Greatest Common Divisor of Strings
Problem
For two strings s and t, we say "t divides s" if and only if s = t + ... + t (t concatenated with itself 1 or more times) Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.
a = "abcabc", b = "abc""abc"from math import gcd
def gcd_of_strings(a, b):
if a + b != b + a:
return ""
return a[: gcd(len(a), len(b))]function gcdOfStrings(a, b) {
if (a + b !== b + a) return "";
const gcd = (x, y) => y === 0 ? x : gcd(y, x % y);
return a.slice(0, gcd(a.length, b.length));
}class Solution {
public String gcdOfStrings(String a, String b) {
if (!(a + b).equals(b + a)) return "";
int x = a.length(), y = b.length();
while (y != 0) { int r = x % y; x = y; y = r; }
return a.substring(0, x);
}
}string gcdOfStrings(string a, string b) {
if (a + b != b + a) return "";
int x = a.size(), y = b.size();
while (y) { int r = x % y; x = y; y = r; }
return a.substr(0, x);
}Explanation
We want the longest string x that, repeated some number of times, builds both inputs. There is a neat shortcut: such an x exists only when the two strings "agree", and when it does, its length is just the gcd of the two lengths.
The agreement check is the line a + b == b + a. If gluing them in either order gives the same result, they are made from the same repeating block; if not, no common base exists and we return the empty string.
When they agree, the answer is the first gcd(len(a), len(b)) characters of a. This works because the shared building block must evenly divide both lengths, and the largest such length is exactly the greatest common divisor.
Example: a = "abcabc", b = "abc". Here a + b == b + a holds, and gcd(6, 3) = 3, so we take the first 3 characters of a → "abc".
Forming the concatenations and comparing them is linear in the total length, and the gcd of the lengths is cheap, so the whole thing runs in linear time.