Greatest Common Divisor of Strings (LC 1071)

Pattern: String check + math → GCD (Euclid’s Algorithm)
Difficulty: Easy
Time: O(n + m) | Space: O(n + m) for the glued strings

Problem

Find the longest string x that builds both str1 and str2 by repeating it.
If there isn’t one, return "".

Core idea

Glue them both ways. Same result? There’s a shared brick, and its length is gcd(len1, len2).

Think of each string as a chain of identical Lego bricks.

1. Glue both ways. If both are made of the same brick, the order doesn’t matter:

   • "ABCABC" + "ABC" → "ABCABCABC"
   • "ABC" + "ABCABC" → "ABCABCABC" ✅ same

   Different bricks show up as a different result:

   • "LEET" + "CODE" → "LEETCODE"
   • "CODE" + "LEET" → "CODELEET" ❌ different → return ""

2. Find the brick size. The biggest brick that fits evenly into both lengths is gcd(len1, len2).

3. Take that many letters from the start of str1.

Example: "ABABAB" (6) and "ABAB" (4) → gcd(6, 4) = 2 → "AB"
Check: "AB" × 3 = "ABABAB", "AB" × 2 = "ABAB" ✅

Code (TypeScript)

function gcdOfStrings(str1: string, str2: string): string {
  if (str1 + str2 !== str2 + str1) return "";
 
  const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));
 
  return str1.slice(0, gcd(str1.length, str2.length));
}

Gotchas

• Don’t search for the brick letter by letter. The glue check already proves one exists.
• The answer is always a prefix, because every repeat starts at the beginning of the string.
• Test these: no shared brick ("LEET", "CODE"), one string inside the other ("ABCABC", "ABC"), equal strings, and lengths that aren’t multiples of each other ("ABABAB", "ABAB").

Why the glue check is enough (deeper)

• Shared brick → same glue. If str1 = X repeated m times and str2 = X repeated n times, both orders give X repeated m + n times.
• Same glue → shared brick. If the glue matches, the shorter string must be the start of the longer one. Cut it off and the leftover passes the same check. The lengths shrink exactly like the GCD steps until you reach the brick.
• Why the biggest one is gcd. Any brick’s length has to divide both lengths, so it can’t be longer than gcd(len1, len2).

Same idea shows up in

• GCD (Euclid’s Algorithm)
• Repeated Substring Pattern (LC 459)