Greatest Common Divisor of Strings
Understanding the Problem
This problem asks us to find the longest string that can be repeated some number of times to form both str1 and str2. Think of it like finding the GCD of two numbers, but for strings instead.
If a string x divides both str1 and str2, then the length of x must divide both len(str1) and len(str2). This means the length of the answer is at most gcd(len(str1), len(str2)), which connects string divisibility to integer GCD.
Matching lengths alone do not guarantee a valid GCD string. For example, "LEET" and "CODE" have gcd(4, 4) = 4, but the two strings share no characters. We need to verify that a common divisor string exists before computing it.
Key Constraints:
1 <= str1.length, str2.length <= 1000→ Lengths up to 1000 leave room for an O(n^2) scan, but a linear solution is available.str1andstr2consist of uppercase English letters. → Direct character comparison is sufficient.
Approach 1: Brute Force (Check All Prefixes)
Intuition
If a string x divides both str1 and str2, then x must be a prefix of both strings. Since we want the largest such string, we can start from the longest possible candidate and work down.
The longest possible candidate cannot exceed the shorter of the two strings. Its length must also divide both len(str1) and len(str2), otherwise repeating it cannot reproduce either string exactly.
So we try every prefix of str1 whose length divides both string lengths, check whether repeating that prefix produces both strings, and return the longest prefix that works.
Algorithm
- Let
minLenbe the minimum oflen(str1)andlen(str2). - Iterate candidate lengths from
minLendown to1. - For each candidate length
len, check iflendivides bothlen(str1)andlen(str2). - If so, extract the prefix
candidate = str1[0..len-1]. - Check if repeating
candidatethe right number of times producesstr1, and separately check forstr2. - If both checks pass, return
candidate. - If no candidate works, return
"".
Example Walkthrough
Code
- Time Complexity: O(min(m, n) * (m + n)). We try up to min(m, n) candidate lengths. For each candidate, building the repeated string and comparing takes O(m + n) work.
- Space Complexity: O(m + n). We build repeated strings for comparison, which can be as long as the input strings.
This tries many candidate lengths before settling on the answer. The next approach computes the correct length directly from the integer GCD and skips the search entirely.
Approach 2: GCD Length + Concatenation Check
Intuition
If a string x divides both str1 and str2, then the length of x must divide both len(str1) and len(str2). Since we want the longest such string, its length must be exactly gcd(len(str1), len(str2)).
So instead of trying every possible prefix, we go straight to the one candidate that could be the answer: the prefix of length gcd(len(str1), len(str2)). Then we verify that this candidate divides both strings.
The concatenation test str1 + str2 == str2 + str1 decides whether any common divisor string exists. One direction is clear: if both strings are repetitions of some base string t (say str1 = t * p and str2 = t * q), then concatenating in either order gives t * (p + q), so the two results are identical. The other direction, that equal concatenations force a shared repeating unit, follows from the Fine and Wilf theorem on periodicity of words. Once existence is established, the longest valid base string has length gcd(len(str1), len(str2)), so its prefix of that length is the answer.
Algorithm
- Check if
str1 + str2equalsstr2 + str1. If not, return"". - Compute
gcdLen = gcd(len(str1), len(str2)). - Return
str1[0..gcdLen-1].
Example Walkthrough
Code
- Time Complexity: O(m + n). Building the two concatenations takes O(m + n). Comparing them takes O(m + n). Computing the integer GCD takes O(log(min(m, n))), which is dominated by the string operations.
- Space Complexity: O(m + n). We create the two concatenated strings for comparison.