Problem 39.1 · Math for Coding InterviewsEasy

Greatest Common Divisor of Strings

What it teaches: GCD applied to string lengths, after a commutativity check.

Practise it on judges as “Greatest Common Divisor of Strings”.

In plain words

Two words are made by repeating a small tile, like "AB" repeated. If both are built from the same tile, gluing them in either order gives the same result. If they are, the biggest shared tile has a length equal to the greatest common divisor of the two lengths.

Return the biggest tile, or "". Example: str1 = "ABABAB", str2 = "ABAB" → "AB".

The problem

Return the largest string x such that both str1 and str2 are made of repeated copies of x, or "".

Example 1

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

Constraints

1 ≤ lengths ≤ 1000

Pattern clues in the wording

→ Common repeating unit

These clues point to Number Theory and Combinatorics: GCD, primes, modular arithmetic, fast power and counting formulas that turn loops into a few lines of math.

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        return "";
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	str1 = "ABCABC" str2 = "ABC"	"ABC"
2	str1 = "ABABAB" str2 = "ABAB"	"AB"
3	str1 = "LEET" str2 = "CODE"	""

From slow to fast

Approaches

1. Concatenation check + GCD · O(n + m)

Concatenation check + GCD

Time O(n + m) Space O(n + m)

Return "" unless str1 + str2 equals str2 + str1; then the prefix of length gcd(len1, len2).

▶ Dry run: Same glue both ways, then GCD of lengthsstr1 = "ABABAB", str2 = "ABAB"

check(vars)

str1 + str2: ABABABABABstr2 + str1: ABABABABABequal: yes

Step 1/3Both orders give the same string, so a common tile exists.

Approach 1

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if (!(str1 + str2).equals(str2 + str1)) return "";
        return str1.substring(0, gcd(str1.length(), str2.length()));
    }

    private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

Verdict: One check and one gcd.

Before you submit

Edge cases and common mistakes

Test these inputs

Identical strings
No common unit

Mistakes people make

Trying every prefix length (works, but slower).

Interview

Follow-up questions

Why does the concatenation test work?

Command Palette

The problem

Approaches

Concatenation check + GCD

Edge cases and common mistakes

Follow-up questions