596. Greatest Common Divisor of Strings
Say a string t divides a string s when s is exactly t glued to itself some whole number of times (once or more). For example, "AB" divides "ABABAB", but does not divide "ABAABB".
You are given two strings str1 and str2 of uppercase English letters. Return the longest string x that divides both str1 and str2.
If the two strings share no divisor at all, return the empty string. When a common divisor exists, the longest one is unique, so the answer is always well-defined.
Example 1:
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
Explanation: "ABC" repeated twice gives str1 and repeated once gives str2, so it divides both. Nothing longer can divide "ABC" itself, so "ABC" is the answer.
Example 2:
Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
Explanation: "AB" copied 3 times gives str1 and copied 2 times gives str2. "ABAB" divides str2 but not str1 (6 is not a multiple of 4), so "AB" is the longest common divisor.
Constraints:
- 1 ≤ str1.length, str2.length ≤ 1000
- str1 and str2 consist of uppercase English letters.
Hints:
Suppose some string x divides both inputs. Then str1 + str2 and str2 + str1 are each just a long row of x-copies — so the two concatenations must be exactly equal. Flip that around: if str1 + str2 differs from str2 + str1, no common divisor can exist.
When the concatenations do match, a common divisor of every viable length exists down the divisor chain — and the longest one has length gcd(len(str1), len(str2)). Compute the gcd of the two lengths with Euclid's algorithm (a, b → b, a mod b until b is 0) and return that prefix of str1.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: str1 = "ABCABC", str2 = "ABC"
Expected output: "ABC"