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.
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); }}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.