Greatest Common Divisor of Strings · Optimal Solution

If the concatenations agree, the GCD of their lengths tells you everything.

A content pipeline checks whether two template fragments share a common repeating tile — like "ABCABC" and "ABC" both being copies of "ABC". Given two strings, find the largest string that divides both. The key insight: if str1 + str2 equals str2 + str1, a common divisor exists, and its length is the GCD of the two string lengths. O(n + m) time. O(n + m) space.

Interactive

Watch the concatenation test and GCD extraction

Concept

Why concatenation order reveals divisibility

The concatenation equality test is both necessary and sufficient for the existence of a common divisor string.

the commutativity test

If both strings are built from the same tile t, then str1 + str2 is just t repeated a + b times — the same regardless of which string comes first. Equal concatenations prove a shared tile exists.

GCD gives the longest tile

If a tile of length k divides both strings, then k divides both len1 and len2. The longest such tile has length GCD(len1, len2) — guaranteed by the Euclidean algorithm.

no brute-force verification needed

Once the concatenation test passes, extracting the first GCD(len1, len2) characters is guaranteed to produce a valid tile. No need to check that it actually tiles both strings — the commutativity already proved it.

Algorithm

One test, one GCD, one substring

No looping over possible divisor lengths. No pattern matching. Just a string comparison, an integer GCD, and a prefix extraction.

  1. 1

    Test concatenation commutativity

    Check whether str1 + str2 === str2 + str1. If not, return the empty string — no common divisor exists.

  2. 2

    Compute GCD of lengths

    Use the Euclidean algorithm: GCD(a, b) = GCD(b, a % b) until b reaches zero. The result is the length of the longest common tile.

  3. 3

    Extract the candidate prefix

    Return str1.substring(0, gcdLength). This prefix tiles both strings and is the greatest common divisor string.

Edge Cases

Where the answer is immediate

Some inputs resolve at the very first check.

No common divisor

When str1 + str2 ≠ str2 + str1, no common tile exists. The concatenation test catches this instantly — no GCD computation needed.

Equal strings

When both strings are identical, GCD(n, n) = n, so the entire string is its own greatest common divisor. The answer is the string itself.

One divides the other

When one string is an exact multiple of the other, the shorter string is the GCD. The Euclidean algorithm reaches zero in one step.