Greatest Common Divisor of Strings
Greatest Common Divisor of Strings is LeetCode 1071 (Easy). A string t divides a string s when s is t written one or more times in a row.
Given str1 and str2, return the longest string that divides both of them, or "" if no string does.
- 1 <= str1.length, str2.length <= 1000
- str1 and str2 consist of English uppercase letters.
Intuition
Two questions settle the answer.
- Is there any common block at all? If both strings are copies of the same block
t, thenstr1 + str2andstr2 + str1are both just copies oft, so they are equal. If the two joins differ, no common block exists. - How long is the longest one? A block that divides a string has a length that divides the string's length. So any common block's length divides both lengths, and the largest possible length is
gcd(len(str1), len(str2)).
When the joins are equal, the prefix of that length really does divide both strings, so it is the answer.
"Repeated some number of times" plus "largest" is divisibility language. When two objects are built from one repeating unit, the largest shared unit usually comes from the gcd of their sizes.
Approach
Before reading on: if str1 = "ABABAB" and str2 = "ABAB", write out str1 + str2 and str2 + str1 and compare them. Then try "LEET" and "CODE". Which number decides how long the answer is? Aim for O(m + n).
Two ways to solve it
One comparison decides whether any block exists, and the gcd of the lengths gives its size.
- No search: the length is computed, not tried.
- Three lines of logic.
The usual interview answer.
Test every prefix length from the longest down and return the first prefix that divides both strings.
- No proof needed: each candidate is checked directly.
- Slower: up to 1,000 lengths, each checked against both strings.
The obvious first idea, and fast enough here.
Both are accepted at these sizes. The join check skips the search entirely, so the steps, code and demo follow it; the search version comes after the demo.
Compare the two joins
If str1 + str2 != str2 + str1, return "". Two strings built from one block give the same result in either order, so a difference proves that no common block exists.
Take the gcd of the lengths
Compute length = gcd(len(str1), len(str2)) with Euclid's algorithm. Every common block has a length that divides both lengths, so none can be longer than this.
Return the prefix of that length
Return str1[:length]. Once the joins match, both strings are copies of one shortest block, and this prefix is a whole number of those blocks that fits both lengths exactly.
Greatest Common Divisor of Strings solution in Python | C++ | Java
str1 + str2 and str2 + str1.str1 and green from str2. Both joins have the same length, 9, so they can be compared letter by letter.str1 and str2 are copies of one common block. What is left is its length, and that depends only on the two lengths.str1 and 1 time into str2 with nothing left over, and no longer block could fit both lengths.str1 + str2 and str2 + str1.str1 and green from str2. Both joins have the same length, 10, so they can be compared letter by letter.str1 and str2 are copies of one common block. What is left is its length, and that depends only on the two lengths.str1 and 2 times into str2 with nothing left over, and no longer block could fit both lengths.str1 + str2 and str2 + str1.str1 and green from str2. Both joins have the same length, 8, so they can be compared letter by letter.Try each block length
A prefix of length k can only divide both strings if k divides both lengths, so skip any other k. For the rest, rebuild each string from copies of the prefix and compare. Going from the longest length down means the first match is the answer.
Common pitfalls
Skipping the join check
length = gcd(len(str1), len(str2)) return str1[:length]
if str1 + str2 != str2 + str1:
return ""
length = gcd(len(str1), len(str2))
return str1[:length]The gcd of two lengths always exists, even when the letters have nothing in common. Without the check, "LEET" and "CODE" give "LEET" instead of "".
Returning the shortest common block
for k in range(1, len(str1) + 1):
if divides(str1[:k], str1) and divides(str1[:k], str2):
return str1[:k]return str1[:gcd(len(str1), len(str2))]
The problem asks for the longest block. For "AAAA" and "AA" the shortest is "A", but "AA" also divides both, so "AA" is the answer.
Checking only that the shorter string is a prefix
if not str1.startswith(str2):
return ""if str1 + str2 != str2 + str1:
return ""A prefix match does not mean the same block repeats. "ABAB" starts with "ABA", yet no string divides both, and the prefix test lets the code return "A".
Edge cases
"ABAB" and "BABA"The joins are "ABABBABA" and "BABAABAB", which differ, so the answer is "" even though both strings repeat a 2-letter block.
"AAA" and "AA"The joins match, and gcd(3, 2) = 1, so the answer is the single letter "A": no longer block fits both a length of 3 and a length of 2.
Complexity
Greatest Common Divisor of Strings FAQ
Why is the gcd prefix guaranteed to divide both strings?
Equal joins mean str1 and str2 commute, and two strings that commute are both copies of one shortest block u. Each length is then a multiple of len(u), so their gcd is too. A prefix whose length is a multiple of len(u) is whole copies of u, and it fits each length exactly.
Can I solve it without building the joined strings?
Yes. Take the prefix t of length gcd(m, n) and check that str1 and str2 are each t repeated m / len(t) and n / len(t) times. It is still O(m + n) time, and the checks can be done with index arithmetic instead of new strings.