Algorithms · interview field notes

GCD of Strings: the largest piece that tiles both

We say t divides s when s is just t glued to itself some whole number of times. Given two strings, find the largest x that divides both. Press Play on each figure and leave able to explain why one gcd and one concatenation settle it — not just type the trick.

("ABCABC", "ABC") → "ABC" · ("ABABAB", "ABAB") → "AB" · ("LEET", "CODE") → ""

How do you find it without testing every prefix length one at a time?

Why does a single s + t vs t + s comparison decide whether any answer exists?

The answer to memorize

One concatenation, one gcd

The whole solution is two lines. Say them cleanly and stop:

Say this

"If str1 + str2 doesn't equal str2 + str1, there's no common divisor — return the empty string. Otherwise the answer is the prefix of length gcd(len1, len2): str1[0, k]. One concatenation check, one gcd — O(n + m)."

That's it. The rest of this page is why those two lines are correct, and how to defend each under pressure — why a gcd, and why that one concatenation test is enough to decide whether any answer exists at all.

The honest starting point

Brute force: every prefix length

A divisor has to be a prefix of both strings, so try each possible length from the shorter string on down, and keep the first that tiles both. Correct, and a fine safety net — but it scans the strings again for every candidate.

Brute force · try every prefix lengthfig

the two strings

str1 = "ABABAB" · len 6

ABABAB

str2 = "ABAB" · len 4

ABAB

Any divisor x must be a prefix of both strings, so the longest it could be is min(6, 4) = 4. Try candidate lengths top‑down; keep the first that tiles both.

01 / 05

The tell: the only lengths that ever pass are the ones dividing both 6 and 4. The biggest such length is their gcd — so the loop is computing a gcd the slow way. That's the compression to reach for.

Solve the integer shadow first

Reduce it to its lengths

Strip away the letters and ask the integer version of the question. The shape left behind is unmistakable.

Reduce the problem to its lengthsfig

str1

ABABAB

str2

ABAB

Here are the two strings again — six tiles and four.

01 / 04

The move

"The largest x that divides both" is, word for word, the definition of greatest common divisor. The string problem is a gcd wearing a costume — and reading it back that way is the highest-leverage habit in the whole cluster.

The payoff

Euclid computes the gcd

We don't list divisors in real code — we run Euclid: replace the larger length with (larger mod smaller) until one hits zero. The survivor is the gcd, and the answer is that-long a prefix.

Euclid's algorithm on the lengthsfig

press play to reduce (6, 4)

6,4

→

4,2

→

2,0

Euclid's algorithm. Take the pair of lengths (6, 4) and repeatedly replace the bigger with (bigger mod smaller), until one of them hits 0.

01 / 04

A handful of cheap steps. In Ruby it collapses to one built-in: str1.length.gcd(str2.length) — then slice that many characters off the front.

The correctness guard

The one check that makes it legal

There's a trap: the gcd-length prefix only tiles both strings when a common root actually exists. One O(n) test settles it — concatenate in both orders and compare. Flip between a case that works and one that doesn't.

The one check · does s + t equal t + s?fig

s + t

ABCABCABC

t + s

ABCABCABC

✓ identical — a common root must exist

Gluing them in either order gives the same string. By the Lyndon–Schützenberger theorem that guarantees both are powers of one common root — so a divisor exists, and it's the length‑gcd prefix "ABC".

one concatenation compare, O(n) — the entire correctness guard in a single line

Say this

"First I check str1 + str2 == str2 + str1. If they differ, no common divisor can exist and I return the empty string. Only when they match do I take the gcd-length prefix."

The theorem behind it

Why that check is enough

The concatenation test isn't a heuristic — it's a theorem. Two strings commute under concatenation if and only if they're both powers of one common root. And the proof is Euclid again, this time running on the strings themselves.

Why the check works · Lyndon–Schützenbergerfig

ABABAB

ABAB

The equal‑concatenation check passed. Here's why that forces a shared root — the proof is just Euclid, run on the strings instead of their lengths.

01 / 04

The name to drop

Lyndon–Schützenberger: string commutation ⟺ a shared primitive root. The induction that proves it strips the shorter string off the longer — the Euclidean algorithm — which is exactly why the root's length comes out to gcd(len1, len2).

The transferable habit

The pattern, and its siblings

Internalize one reflex: when a problem is about exact repetition or even division, restate it in terms of lengths or counts, then check whether you've just written the definition of gcd or lcm. That single move catches a whole family of problems that all rhyme.

“Largest tile that fills both strings?”gcd

This problem. The longest common period is the gcd of the two lengths.

“Do these two repeating patterns ever realign?”lcm

Cycles of length a and b sync back up after lcm(a, b) steps.

“Smallest repeating unit of a string?”period

The period is n − failure[n] (KMP) — and it's a true period only when that length divides n. Divisibility again.

“Can a k×k tile fill an a×b floor cleanly?”gcd

Exactly when k divides gcd(a, b) — the largest square that tiles both sides.

“When does a permutation return every element home?”lcm

After the lcm of all its cycle lengths.

“Are these two ratios equal in lowest terms?”gcd

Divide each pair by its gcd, then compare — the same reduction, on numbers.

What trips people up

The edge cases that break naive code

Four traps an interviewer will probe — each one is dispatched by the two-line solution, as long as you keep both lines.

skipping the concat check

Jumping straight to the gcd-length prefix is wrong. For "ABAB" / "ABCD" the lengths share gcd 4, yet "ABAB" can't tile "ABCD". The concatenation test sees they differ and returns "".

gcd, not min(len)

The answer's length is gcd(len1, len2), not the shorter length. A min-length prefix need not divide the longer string evenly.

the empty answer is real

When nothing divides both (LEET / CODE), return the empty string "" — explicitly. Don't let it fall through to nil.

either string works

Once a common root exists, str1[0, k] and str2[0, k] are identical. Take the prefix from whichever — no need to compare them.

Print this on the back of your hand

The interview cheat-sheet

“What's the approach?”

If str1 + str2 != str2 + str1, return "". Otherwise return str1[0, gcd(len1, len2)]. O(n + m) time.

“Why does it work?”

Equal concatenation ⟺ both strings are powers of one common root (Lyndon–Schützenberger). The longest such root has length gcd(len1, len2).

“Why the concat check?”

It's the O(n) test for whether any common root exists. Skip it and the gcd-length prefix can fail to tile — you'd return a wrong, non-empty string.

“Don't forget…”

Length is gcd, not min. Return "" when there's none. The prefix of either string is the same once a root exists.

the whole solution · rubyO(n + m)

def gcd_of_strings(str1, str2)

  # No shared base unit -> no divisor can exist.

  return "" if str1 + str2 != str2 + str1

  # The answer's length is the gcd of the two lengths;

  # it is that-long a prefix of either string.

  k = str1.length.gcd(str2.length)

  str1[0, k]

end

Every Ruby Integer ships a .gcd method — 12.gcd(8) ⟶ 4 — so the famous trick is genuinely two lines. str1[0, k] reads "from index 0, take k characters."

The one-liner to land

"Two strings share a divisor iff str1 + str2 == str2 + str1; when they do, the biggest one is the prefix of length gcd(len1, len2). That concatenation equality is the Euclidean algorithm's promise in disguise — which is exactly why a gcd of lengths gives the answer."