Greatest Common Divisor of Strings
Last Updated: March 28, 2026
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)). That is the key mathematical insight connecting string divisibility to integer GCD.
But there is an important catch. Just because the lengths line up does not mean a valid GCD string exists. For example, "LEET" and "CODE" have gcd(4, 4) = 4, but the strings have completely different characters. We need a way to verify that a common divisor string actually exists before computing it.
Key Constraints:
1 <= str1.length, str2.length <= 1000→ With lengths up to 1000, even O(n^2) is comfortably within limits. But we can do much better.str1andstr2consist of uppercase English letters. → No special characters to worry about. Simple character comparison is sufficient.
Approach 1: Brute Force (Check All Prefixes)
Intuition
The most natural first thought: if some string x divides both str1 and str2, then x must be a prefix of both strings. And since we want the largest such string, we can start from the longest possible candidate and work our way down.
What is the longest possible candidate? It cannot be longer than the shorter of the two strings. And its length must divide both len(str1) and len(str2), otherwise you could not repeat it to form either string exactly.
So the approach is: try every prefix of str1 whose length divides both string lengths, check if repeating that prefix produces both strings, and return the longest one 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 approach works but tries many unnecessary candidates. What if we could jump directly to the correct candidate length using the mathematical GCD?
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 can jump straight to the one candidate that could be the answer: the prefix of length gcd(len(str1), len(str2)). Then we just need to verify that this candidate actually divides both strings.
If str1 + str2 == str2 + str1, then both strings are built from the same repeating unit. This is guaranteed by the Lyndon-Schutzenberger theorem from combinatorics on words. 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 results are identical. The longest such base string has length gcd(len(str1), len(str2)).
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.