Greatest Common Divisor of Strings
Easy GCD on lengths
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
A string t "divides" s if s is t repeated some number of times. Return the longest string that divides both inputs, or "" if none.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest block that, repeated, builds both strings.
Why this works: if both strings are made of the same block, gluing them in either order gives the same text. The block length must divide both lengths, and the longest such length is their GCD.
Example: str1 = "ABCABC", str2 = "ABC"
"ABCABC"+"ABC" == "ABC"+"ABCABC" ✓gcd(6, 3) = 3 → "ABC"
✦Hints open one at a time
↗Approach
Check the concatenation trick first. If s1 + s2 equals s2 + s1, both are built from the same block, and the longest block has length gcd of the two lengths.
</>Solution (Java)
class Solution {
public String gcdOfStrings(String str1, String str2) {
if (!(str1 + str2).equals(str2 + str1)) return "";
return str1.substring(0, gcd(str1.length(), str2.length()));
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}!Common mistake
Trying every prefix length and checking divisibility by brute force, which is much slower and easy to get wrong.
- Time: O(n + m) for the string comparison.
- Space: O(n + m) for the concatenations.
