Greatest Common Divisor of Strings
EasyPrompt
For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + t + t (i.e., t is concatenated with itself one or more times).
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.
Example 1:
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"Example 2:
Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"Example 3:
Input: str1 = "LEET", str2 = "CODE"
Output: ""
Constraints:
1 <= str1.length, str2.length <= 1000str1andstr2consist of English uppercase letters.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves checking every possible prefix of the shorter string, from longest to shortest, to see if it can be a common divisor for both str1 and str2.
Algorithm
- Get the lengths of
str1andstr2, let's call themlen1andlen2. - Iterate with a loop variablelfrommin(len1, len2)down to1. - In each iteration, extract acandidateprefix fromstr1of lengthl. - Check if thiscandidatestring divides bothstr1andstr2using a helper function. - The helper functionisDivisor(s, p)checks ifs.length()is divisible byp.length()and ifscan be constructed by repeatingp. - If thecandidatedivides both strings, it is the largest one found so far (due to the descending loop), so return it. - If the loop completes without finding a common divisor, return an empty string"".
Walkthrough
The core idea is to test all potential candidates for the greatest common divisor string x. A candidate for x must be a prefix of str1. We can iterate through all possible lengths l for this prefix, starting from the length of the shorter string down to 1. For each length l, we extract the prefix p = str1.substring(0, l). We then define a helper function, isDivisor(s, p), which checks if string s is formed by concatenating p one or more times. This check involves two steps: first, the length of s must be divisible by the length of p, and second, s must be equal to p repeated s.length() / p.length() times. In the main loop, for each prefix, we call isDivisor(str1, prefix) and isDivisor(str2, prefix). The first (and therefore longest) prefix for which both checks return true is the answer. If no such prefix is found after checking all possible lengths, we return an empty string. ```java
class Solution {
public String gcdOfStrings(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
for (int l = Math.min(len1, len2); l >= 1; l--) {
String candidate = str1.substring(0, l);
if (isDivisor(str1, candidate) && isDivisor(str2, candidate)) {
return candidate;
}
}
return "";
}
private boolean isDivisor(String s, String p) { int len_s = s.length(); int len_p = p.length(); if (len_s % len_p != 0) { return false; } int times = len_s / len_p; StringBuilder sb = new StringBuilder(); for (int i = 0; i < times; i++) { sb.append(p); } return s.equals(sb.toString());}}
Complexity
Time
O(min(n, m) * (n + m)), where `n` and `m` are the lengths of the two strings. The loop runs `min(n, m)` times. Inside the loop, the `isDivisor` check for `str1` takes O(n) time and space, and for `str2` it takes O(m) time and space.
Space
O(n + m) to store the temporary strings built inside the `isDivisor` helper function for comparison.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem by exhaustively checking all possibilities.
Cons
Highly inefficient, especially for long strings, as it involves many string operations (substring, concatenation, comparison) inside a loop.
Creates many temporary strings, leading to high memory usage.
This approach improves upon the brute-force method by recognizing a key property: if a string x divides str1, then the length of x must be a divisor of the length of str1. Therefore, we only need to check lengths that are common divisors of both string lengths.
Algorithm
- Get the lengths of
str1andstr2,len1andlen2. - Iterate with a loop variablelfrommin(len1, len2)down to1. - Inside the loop, add a condition:if (len1 % l == 0 && len2 % l == 0). - Only iflis a common divisor of the lengths, proceed with the check. - Extract thecandidateprefix fromstr1of lengthl. - Use the sameisDivisorhelper function to check if thecandidatedivides bothstr1andstr2. - If it does, return thecandidate. - If the loop finishes, return"".
Walkthrough
We can significantly optimize the previous approach. Instead of checking every possible prefix length l, we only need to check lengths that are common divisors of both str1.length() and str2.length(). The algorithm iterates from l = min(len1, len2) down to 1. In each iteration, it first checks if l is a divisor of both len1 and len2. Only if l is a common divisor do we proceed to check if the prefix of that length is the actual string divisor. This reduces the number of times we perform the expensive isDivisor check, leading to a faster solution in practice, although the worst-case time complexity remains the same. ```java
class Solution {
public String gcdOfStrings(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
for (int l = Math.min(len1, len2); l >= 1; l--) {
if (len1 % l == 0 && len2 % l == 0) {
String candidate = str1.substring(0, l);
if (isDivisor(str1, candidate) && isDivisor(str2, candidate)) {
return candidate;
}
}
}
return "";
}
private boolean isDivisor(String s, String p) { int len_s = s.length(); int len_p = p.length(); int times = len_s / len_p; StringBuilder sb = new StringBuilder(); for (int i = 0; i < times; i++) { sb.append(p); } return s.equals(sb.toString());}}
Complexity
Time
O(min(n, m) * (n + m)). While the number of checks is reduced to the number of common divisors, the worst-case complexity is bounded by the same factors as the naive approach. However, it is significantly faster on average.
Space
O(n + m) for the temporary strings built in the `isDivisor` helper function.
Trade-offs
Pros
More efficient in practice than the naive brute-force by reducing the number of expensive string checks.
Still relatively easy to understand.
Cons
Still relies on string construction and comparison within a loop.
The worst-case time complexity is not an improvement over the naive approach.
This is the most efficient approach, which leverages a mathematical property of strings. If a string x is a common divisor of str1 and str2, then str1 + str2 must be equal to str2 + str1.
Algorithm
- First, check the fundamental property: concatenate
str1andstr2in both orders (str1 + str2andstr2 + str1). - If(str1 + str2)is not equal to(str2 + str1), then no common divisor exists. Return"". - If they are equal, a common divisor is guaranteed to exist. - Calculate the greatest common divisor (GCD) of the lengths ofstr1andstr2. Let this begcdLength. - The result is the prefix ofstr1(orstr2) of lengthgcdLength. Returnstr1.substring(0, gcdLength).
Walkthrough
This optimal solution is based on a crucial property: a common string divisor x exists for str1 and str2 if and only if str1 + str2 equals str2 + str1. If this condition is false, no common divisor can exist. If it's true, it guarantees that both strings are made of repetitions of some base string. The largest such base string (our answer) will have a length equal to the greatest common divisor (GCD) of the lengths of str1 and str2. The algorithm is therefore very simple and efficient. ```java
class Solution {
public String gcdOfStrings(String str1, String str2) {
// Check if they have a common divisor property
if (!(str1 + str2).equals(str2 + str1)) {
return "";
}
// If they do, the length of the GCD string is the GCD of their lengths int gcdLength = gcd(str1.length(), str2.length()); return str1.substring(0, gcdLength);} // Helper method to compute GCD using Euclidean algorithmprivate int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a;}}
Complexity
Time
O(n + m), where `n` and `m` are the lengths of the strings. This is dominated by the string concatenation and subsequent equality check. The GCD calculation is much faster, `O(log(min(n, m)))`.
Space
O(n + m) to store the two concatenated strings for the comparison.
Trade-offs
Pros
Extremely efficient with linear time complexity.
Elegant and concise solution.
Cons
Relies on a non-obvious mathematical property of strings (related to Fine & Wilf's theorem on periodicity), which might be difficult to derive from scratch.
Solutions
Solution
class Solution {public String gcdOfStrings(String str1, String str2) { if (!(str1 + str2).equals(str2 + str1)) { return ""; } int len = gcd(str1.length(), str2.length()); return str1.substring(0, len); }private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }}class Solution {public: string gcdOfStrings(string str1, string str2) { if (str1 + str2 != str2 + str1) return ""; int n = __gcd(str1.size(), str2.size()); return str1.substr(0, n); }};class Solution: def gcdOfStrings(self, str1: str, str2: str) -> str: def check(a, b): c = "" while len(c) < len(b): c += a return c == b for i in range(min(len(str1), len(str2)), 0, - 1): t = str1[: i] if check(t, str1) and check(t, str2): return t return ''Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.