Greatest Common Divisor of Strings

Problem in Plain English

Return the longest string whose repetitions form both input strings. Check compatibility before applying Euclidean GCD to their lengths.

Problem Statement

A nonempty string x divides a string s when s consists of one or more copies of x. Given str1 and str2, return the longest string dividing both, or the empty string if none exists. The official exercise uses uppercase English letters.

Constraints

1 <= str1.length, str2.length <= 1000.
Each string contains only uppercase English letters.

Examples

Example 1

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Concatenations both equal ABCABCABC. Length gcd(6,3)=3 gives prefix ABC.

Example 2

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Both are copies of AB. Euclid computes gcd(6,4)=gcd(4,2)=2, so a four-character prefix is too long.

Example 3

Input: str1 = "BLUE", str2 = "CODE"
Output: ""

BLUECODE differs from CODEBLUE. Equal lengths alone do not imply a common divisor string.

Example 4

Input: str1 = "A", str2 = "A"
Output: "A"

The one-character strings commute and their length GCD is one.

Intuition

A common repeating block makes str1+str2 and str2+str1 identical. If concatenation order changes the characters, no common block exists, even when the lengths share a divisor. Once compatibility is established, the longest block has length gcd(m,n). In Example 1, ABCABC and ABC commute, their lengths are 6 and 3, and the length GCD is 3, so return ABC.

Approaches

Euclidean GCD

Optimal

Solution Details

Reveal Euclidean GCD: intuition, complexity, and code

Intuition

Compare the two concatenation orders, then repeatedly replace the length pair (a,b) with (b,a mod b). The loop stops with b=0 and a equal to their GCD. Return the first a characters of str1. Testing every prefix would repeatedly scan strings; compatibility reduces the content question to one linear check followed by a logarithmic integer calculation.

Step-by-Step Logic

Build str1+str2 = ABCABCABC.
Build str2+str1 = ABCABCABC and confirm equality.
Initialize a=6, b=3.
Compute remainder 6 mod 3=0; replace (a,b) with (3,0).
Stop at b=0 and return str1’s first 3 characters, ABC.

Why It Works

If a common string divides both, both concatenations are copies of that string, so compatibility is necessary. For sufficiency, let commuting nonempty strings u,v satisfy |u|>=|v|. Equality uv=vu forces v to be a prefix of u, so write u=vw and cancel v to obtain wv=vw. Repeating this reduction reaches a common word; taking its primitive root shows that both original strings are powers of one primitive word. Therefore a prefix whose length is a common multiple of the primitive length and divides both original lengths also tiles both; gcd(m,n) has these properties and is the largest possible divisor length. In Euclid, a=q×b+r: a divisor of a and b divides r, and a divisor of b and r divides a. Thus replacing (a,b) by (b,r) preserves exactly the common divisors. The nonnegative remainder decreases until zero, where gcd(a,0)=a.

Dry Run

Euclidean GCD: variable states at each step
Stage	Compatibility / a	b	Remainder	Result
Compare	ABCABCABC = ABCABCABC	none	none	compatible
Initialize lengths	6	3	none	pending
Euclid	6	3	0	next (3,0)
Stop	3	0	none	length 3
Prefix	str1[0:3]	none	none	"ABC"

Complexity Analysis

Time Complexity

O(m + n)

Space Complexity

O(m + n)

Concatenation and comparison cost linear time and create two combined strings. Euclid takes logarithmically many bounded integer remainders, dominated by the string work. Returning a prefix also copies at most min(m,n) characters. No recursive calls or numeric precision risk occur at lengths at most 1000.

Code

Solution.java

1class Solution {2    public String gcdOfStrings(String str1, String str2) {3        if (!(str1 + str2).equals(str2 + str1)) return "";4        int a = str1.length(), b = str2.length();5        while (b != 0) {6            int remainder = a % b;7            a = b; b = remainder;8        }9        return str1.substring(0, a);10    }11}

Hints

Hint 1

A common repeating word makes concatenation order irrelevant.

Hint 2

After verifying that order check, a divisor word’s length must divide both lengths.

Hint 3

Compute the length GCD with (a,b)→(b,a mod b), then return that many prefix characters.

Edge Cases

Equal lengths but different contents must return empty.
Identical strings return the whole string, even if it has a shorter primitive period.
Length GCD one does not bypass the compatibility check.

Common Mistakes and Interview Tips

Returning a gcd-length prefix without checking content fails BLUE and CODE.
Using substring containment instead of exact repetitions permits partial trailing copies.
Overwriting a before calculating a mod b corrupts the Euclidean transition.

Key Takeaway

Separate structural compatibility from numeric size. Euclid works because subtracting multiples preserves the set of common divisors, while remainders make progress.