Greatest Common Divisor of Strings
Greatest Common Divisor of Strings: return the longest string x such that x repeated some number of times equals str1, and x repeated some number of times equals str2.
- 1 <= str1.length, str2.length <= 1000
- str1 and str2 consist of English uppercase letters.
Intuition
If any common divisor string exists at all, both inputs are built from the same repeating block — which forces str1 + str2 and str2 + str1 to be identical. Once that holds, the divisor's length is exactly gcd(len(str1), len(str2)), so the answer is simply that many characters from the front.
The signal is 'greatest' plus 'repeated some number of times' — divisibility language applied to strings. Whenever a structure is built from a repeating unit, questions about the largest common unit reduce to gcd on the sizes. The concatenation-equality trick is the reusable piece; it also settles Repeated Substring Pattern and Rotate String.
Approach
Before reading on: if both strings are made of the same repeating block, what must be true of str1 + str2 compared with str2 + str1? And once you know a divisor exists, what fixes its length? Aim for O(n + m).
The concatenation test decides existence
Suppose a common divisor x exists. Then str1 is x repeated a times and str2 is x repeated b times, so str1 + str2 is x repeated a + b times — and so is str2 + str1. The two concatenations must therefore be equal. The converse is also true: if str1 + str2 == str2 + str1, the strings are powers of a common block. So this single equality check answers the existence question completely, and if it fails the answer is the empty string with no further work.
Why the length is exactly gcd of the lengths
A divisor of length L must divide len(str1) evenly and len(str2) evenly, so L is a common divisor of the two lengths — meaning L divides gcd(len1, len2). The greatest such string therefore has length exactly gcd(len1, len2). This is the same argument as for numbers, lifted to strings: divisibility of the repeating block corresponds precisely to divisibility of the lengths. Python's math.gcd computes it in O(log min(len1, len2)).
Reading off the answer
Given that the concatenation test passed and the length is g = gcd(len1, len2), the answer is str1[:g]. No verification loop is needed — the equality test already guaranteed both strings are powers of a common block, and the gcd argument fixes the block's length, so the first g characters are necessarily that block. Total cost is O(n + m) for building and comparing the concatenations, which dominates the logarithmic gcd.
Solution & live demo
Common pitfalls
Returning the shortest repeating unit
# find the smallest block that builds both return smallest_unit
length = gcd(len(str1), len(str2)) return str1[:length]
The problem asks for the greatest common divisor. On "AAAA" and "AA" the smallest unit is "A", but the correct answer is "AA" — the largest block that divides both.
Skipping the existence check
length = gcd(len(str1), len(str2)) return str1[:length]
if str1 + str2 != str2 + str1:
return ""
# then take the gcd prefixThe gcd of the lengths always exists, so without the equality test the code returns a prefix even when no common divisor does. "LEET" and "CODE" would wrongly yield "L" instead of "".
Brute-forcing every candidate length
for L in range(min(len(str1), len(str2)), 0, -1):
if valid(str1, str2, L):
return str1[:L]length = gcd(len(str1), len(str2))
It works but does O(n·m) verification when the mathematics already pins the length exactly. The gcd argument is the point of the problem — the brute force sidesteps the insight the question is testing.
Edge cases
The concatenation test fails and the empty string is returned.
gcd(n, n) = n, so the whole string is returned.
gcd(6, 3) = 3, giving "ABC".
gcd(4, 2) = 2 yields "AA", which is correct — not the shorter "A", because the greatest divisor is wanted.
The concatenations differ, so it correctly returns the empty string.