Greatest Common Divisor of Strings
The briefingthe full drill, in my own words
The drill: Find the longest string that both inputs are built from by repeating it whole-number-of-times — a divisor here means the string tiles perfectly, no partial copy left over. No shared divisor means the answer is empty.
Two strings arrive, and the question is whether some shorter string can be repeated a whole number of times to rebuild each of them exactly, with no partial copy left dangling at the end.
When such a building-block string exists for both inputs, the drill wants the longest one that works for both simultaneously — the greatest common tile, in the same spirit as a greatest common divisor of two numbers.
If the two strings share no such common tile at all, not even a single matching run that divides both evenly, the expected result is an empty string.
- each string holds up to a few thousand characters
- characters are uppercase English letters
- a valid tile must divide both string lengths evenly, with zero leftover
- no shared tile at all means the answer is an empty string
The hintstake only what you need
HINT 1 THE NUDGE
A string only 'divides' another if repeating it some whole number of times reproduces that string exactly — so any candidate divisor's length has to divide both input lengths evenly. That already rules most lengths out.
HINT 2 THE STRUCTURE
If both strings truly share a common building block, swapping their order and gluing them together changes nothing: str1 + str2 must equal str2 + str1. That single check tells you a shared divisor exists at all, without trying any candidate.
HINT 3 ONE STEP FROM THE ANSWER
Once str1 + str2 == str2 + str1 holds, the longest shared tile is exactly the length gcd(len(str1), len(str2)) — take that prefix of either string and it's the answer.
Coach's boardthe pattern, step by step
str1='RSRSRS' (len 6), str2='RSRS' (len 4). A shared tile exists exactly when str1+str2 equals str2+str1.
The splitstwo paces, two languages
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if str1 + str2 != str2 + str1:
return ""
g = math.gcd(len(str1), len(str2))
return str1[:g]class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
def divides(s: str, candidate: str) -> bool:
if len(s) % len(candidate) != 0:
return False
return candidate * (len(s) // len(candidate)) == s
shorter = str1 if len(str1) <= len(str2) else str2
for length in range(len(shorter), 0, -1):
candidate = shorter[:length]
if divides(str1, candidate) and divides(str2, candidate):
return candidate
return ""class Solution {
public String gcdOfStrings(String str1, String str2) {
if (!(str1 + str2).equals(str2 + str1)) {
return "";
}
int g = gcd(str1.length(), str2.length());
return str1.substring(0, g);
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}class Solution {
public String gcdOfStrings(String str1, String str2) {
String shorter = str1.length() <= str2.length() ? str1 : str2;
for (int length = shorter.length(); length >= 1; length--) {
String candidate = shorter.substring(0, length);
if (divides(str1, candidate) && divides(str2, candidate)) {
return candidate;
}
}
return "";
}
private boolean divides(String s, String candidate) {
if (s.length() % candidate.length() != 0) {
return false;
}
StringBuilder rebuilt = new StringBuilder();
int copies = s.length() / candidate.length();
for (int i = 0; i < copies; i++) {
rebuilt.append(candidate);
}
return rebuilt.toString().equals(s);
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED