Greatest Common Divisor of Strings — Problem & Solution
Greatest Common Divisor of Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Greatest Common Divisor of Strings is an easy coding problem on strings and math, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Strings, Math
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
For strings s and t, we say t divides s if s equals t repeated some whole number of times.
Given str1 and str2, return the largest string x that divides both. If no such string exists, return the empty string.
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:
Explanation: No common divisor string exists.
Constraints
1 <= str1.length, str2.length <= 1000Both strings consist of uppercase English letters.
Hints for Greatest Common Divisor of Strings
Hint 1
If a common divisor exists, both strings are built from the same repeating block — so their concatenations in either order must match.
Hint 2
str1 + str2 == str2 + str1is exactly the condition for a common divisor to exist.Hint 3
When it holds, the answer's length is
gcd(len(str1), len(str2)).
How to solve Greatest Common Divisor of Strings
Strings under concatenation behave like numbers under addition here: a common divisor string exists iff the two commute, and its length is the gcd of the lengths.
Approach
- If
str1 + str2 != str2 + str1, return the empty string. - Otherwise compute
g = gcd(len(str1), len(str2)). - Return the first
gcharacters ofstr1.
Why it works
If both strings are powers of a common block x, concatenation is commutative because both sides reduce to the same run of x. Conversely, commuting forces a common block. Its length must divide both lengths, and the largest such length is their gcd.
Complexity
- Time —
O(n + m) - Space —
O(n + m) for the concatenations
Pitfalls
- Trying every prefix length and testing divisibility is O(n²) and easy to get subtly wrong on the repetition check.
- Skipping the commutation test and just returning the gcd-length prefix answers
"LE"for"LEET"/"CODE". - The gcd must be taken over the lengths, not the strings.
Reference solution
Python
def gcdOfStrings(str1: str, str2: str) -> str:
from math import gcd
if str1 + str2 != str2 + str1:
return ""
return str1[:gcd(len(str1), len(str2))]Java
public static String gcdOfStrings(String str1, String str2) {
if (!(str1 + str2).equals(str2 + str1)) return "";
int a = str1.length(), b = str2.length();
while (b != 0) { int t = a % b; a = b; b = t; }
return str1.substring(0, a);
}C++
string gcdOfStrings(string str1, string str2) {
if (str1 + str2 != str2 + str1) return "";
int a = (int) str1.size(), b = (int) str2.size();
while (b != 0) { int t = a % b; a = b; b = t; }
return str1.substr(0, a);
}JavaScript
var gcdOfStrings = function(str1, str2) {
function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); }
if (str1 + str2 !== str2 + str1) return "";
return str1.slice(0, gcd(str1.length, str2.length));
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings