Greatest Common Divisor of Strings

Easy
514.

Greatest Common Divisor of Strings

Greatest Common Divisor of Strings is an easy coding problem on strings and math, asked in Amazon, Google and Microsoft interviews.

For strings s and t, we say t divides s if s equals t repeated some whole number of times.

Given str1 and str2, return the largest string x that divides both. If no such string exists, return the empty string.

Example 1

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

Example 2

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

Example 3

Input
str1 = "LEET", str2 = "CODE"
Output
Explanation
No common divisor string exists.

Constraints

  • 1 <= str1.length, str2.length <= 1000
  • Both strings consist of uppercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function(str1, str2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Greatest Common Divisor of Strings — Problem & Solution

Greatest Common Divisor of Strings solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Greatest Common Divisor of Strings is an easy coding problem on strings and math, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Strings, Math
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

For strings s and t, we say t divides s if s equals t repeated some whole number of times.

Given str1 and str2, return the largest string x that divides both. If no such string exists, return the empty string.

Example 1

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

Example 2

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

Example 3

Input: str1 = "LEET", str2 = "CODE"
Output: 
Explanation: No common divisor string exists.

Constraints

  • 1 <= str1.length, str2.length <= 1000
  • Both strings consist of uppercase English letters.

Hints for Greatest Common Divisor of Strings

  1. Hint 1

    If a common divisor exists, both strings are built from the same repeating block — so their concatenations in either order must match.

  2. Hint 2

    str1 + str2 == str2 + str1 is exactly the condition for a common divisor to exist.

  3. Hint 3

    When it holds, the answer's length is gcd(len(str1), len(str2)).

How to solve Greatest Common Divisor of Strings

Strings under concatenation behave like numbers under addition here: a common divisor string exists iff the two commute, and its length is the gcd of the lengths.

Approach

  1. If str1 + str2 != str2 + str1, return the empty string.
  2. Otherwise compute g = gcd(len(str1), len(str2)).
  3. Return the first g characters of str1.

Why it works

If both strings are powers of a common block x, concatenation is commutative because both sides reduce to the same run of x. Conversely, commuting forces a common block. Its length must divide both lengths, and the largest such length is their gcd.

Complexity

  • Time — O(n + m)
  • Space — O(n + m) for the concatenations

Pitfalls

  • Trying every prefix length and testing divisibility is O(n²) and easy to get subtly wrong on the repetition check.
  • Skipping the commutation test and just returning the gcd-length prefix answers "LE" for "LEET"/"CODE".
  • The gcd must be taken over the lengths, not the strings.

Reference solution

Python

def gcdOfStrings(str1: str, str2: str) -> str:
    from math import gcd
    if str1 + str2 != str2 + str1:
        return ""
    return str1[:gcd(len(str1), len(str2))]

Java

public static String gcdOfStrings(String str1, String str2) {
    if (!(str1 + str2).equals(str2 + str1)) return "";
    int a = str1.length(), b = str2.length();
    while (b != 0) { int t = a % b; a = b; b = t; }
    return str1.substring(0, a);
}

C++

string gcdOfStrings(string str1, string str2) {
    if (str1 + str2 != str2 + str1) return "";
    int a = (int) str1.size(), b = (int) str2.size();
    while (b != 0) { int t = a % b; a = b; b = t; }
    return str1.substr(0, a);
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings