GCD of Strings LeetCode 1071 Guide

LeetCode 1071 asks you to find the largest string x such that x divides both str1 and str2. A string t divides string s if s equals t repeated some integer number of times. For example, "AB" divides "ABAB" (repeated 2 times) and "ABABAB" (repeated 3 times).

The problem is asking for the GCD of two strings — the longest string that is a prefix of both and whose repetition builds both. If no such string exists (the two strings share no common repeating unit), return an empty string.

This maps a classic number theory concept onto strings. Just as the integer GCD of 6 and 9 is 3, the string GCD of "ABCABC" and "ABC" is "ABC" — the longest string that divides both.

The key insight is: a common divisor string exists if and only if str1 + str2 == str2 + str1. This single equality check tells you whether both strings are built from the same repeating unit. If the check fails, return "" immediately.

If the check passes, the GCD string has length gcd(len(str1), len(str2)), and the answer is str1[:gcd(len(str1), len(str2))]. Python's math.gcd handles this in one line. The full solution is two lines of logic after the check.

This is one of the cleanest solutions in LeetCode — a mathematical observation reduces a seemingly complex string problem to a single comparison plus one integer GCD computation.

If both strings are multiples of a base string t — meaning str1 = t * k1 and str2 = t * k2 — then str1+str2 = t*(k1+k2) and str2+str1 = t*(k2+k1). Since addition is commutative, both concatenations equal t repeated (k1+k2) times. So they must be equal.

Conversely, if the two strings are NOT built from the same base, the concatenations differ. The characters in the middle of str1+str2 (where str1 ends and str2 begins) would not align with the repeating pattern of str2+str1. The equality serves as a proof that a shared base exists.

This is an if-and-only-if relationship: str1+str2 == str2+str1 precisely when a common string divisor exists. You never need to iterate over possible prefix lengths or check divisibility manually — the concatenation test is sufficient.

Once the concatenation check passes and you know a common divisor exists, the longest one has length equal to gcd(len(str1), len(str2)). This follows from the same logic as integer GCD: if a length d divides both len1 and len2, the longest such d is their GCD.

The proof mirrors Euclid's algorithm for integers: if t divides str1 (length m) and str2 (length n), then t also divides str1 − (m/n)*str2 (the remainder), which is the string GCD step. The algorithm terminates when the remainder is zero, leaving the GCD string.

Because the answer is always a prefix of both strings (the common unit always starts both), you simply take str1[:gcd_len] to get the result. No need to verify — the concatenation check already guaranteed a common divisor exists.

Example 1: str1="ABCABC", str2="ABC". Concatenation check: "ABCABCABC" == "ABCABCABC" → true. gcd(6, 3) = 3. Return str1[:3] = "ABC". Correct: "ABC" repeated 2 times gives str1, repeated 1 time gives str2.

Example 2: str1="ABABAB", str2="ABAB". Concatenation check: "ABABABABAB" == "ABABABABAB" → true. gcd(6, 4) = 2. Return str1[:2] = "AB". Correct: "AB" repeated 3 times gives str1, repeated 2 times gives str2.

Example 3 (no divisor): str1="LEET", str2="CODE". Concatenation check: "LEETCODE" != "CODELEET" → false. Return "". No common repeating unit exists between these two strings.

Python solution: import math; return str1[:math.gcd(len(str1), len(str2))] if str1+str2 == str2+str1 else "". This is a genuine one-liner. The math.gcd call handles the Euclidean algorithm, and slicing extracts the prefix. Time: O(m+n) for the concatenation comparison. Space: O(m+n) for the temporary concatenated strings.

Java solution: if (!(str1+str2).equals(str2+str1)) return ""; int gcd = gcd(str1.length(), str2.length()); return str1.substring(0, gcd); with a helper int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }. Java lacks a built-in gcd for integers, so a two-line recursive helper suffices.

Both solutions run in O(m+n) time dominated by the string concatenation and comparison step. The gcd computation is O(log(min(m,n))) which is negligible. Space is O(m+n) for the two temporary strings created during the concatenation check.

GCD of Strings belongs to a family of string pattern problems where mathematical structure underlies the solution. Longest Common Prefix (LeetCode 14) finds the shared beginning of an array of strings — a related concept but solved differently using vertical scanning or binary search.

Valid Anagram (LeetCode 242) tests whether two strings are rearrangements of each other using character frequency counting. Encode and Decode Strings (LeetCode 271) tests understanding of string boundaries and delimiters. These form the "string structure" family that frequently appears in coding interviews.

On the math side, any problem involving divisibility, periodicity, or repeating patterns in strings will often reduce to integer GCD. The KMP failure function for string period detection is another tool in this family — it finds the shortest repeating unit in O(n) time for a single string.