Greatest Common Divisor of Strings

How it works

We can avoid the concatenation check (which requires O(m+n) space) by directly validating the divisor property. Compute the GCD of the lengths, then verify that every character in both strings matches the corresponding character in the first g characters, using modular indexing.

Steps

1. Compute g = gcd(len(str1), len(str2)).
2. For each index i in str1, verify str1[i] == str1[i % g].
3. For each index i in str2, verify str2[i] == str1[i % g].
4. If all checks pass, return str1[:g].
5. Otherwise, return an empty string.

Complexity

• Time complexity: O(m + n)
• Space complexity: O(g) for the output string.

Where m is the length of the string str1, n is the length of the string str2, and g is the GCD of m and n.

Things to watch for

Skipping the Concatenation Check

The key insight is that if a common divisor string exists, then str1 + str2 must equal str2 + str1. Skipping this check and directly returning str1[:gcd(len1, len2)] will produce wrong answers for cases where no valid divisor exists, such as str1 = "LEET" and str2 = "CODE".

Confusing GCD of Lengths with GCD of Strings

The GCD of the string lengths tells you the candidate divisor length, but it does not guarantee that the prefix of that length actually divides both strings. You must verify that the candidate pattern repeats correctly to form both original strings, either through the concatenation check or by explicitly validating the pattern.

from math import gcd

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        g = gcd(len(str1), len(str2))

        if all(str1[i] == str1[i % g] for i in range(len(str1))) and \
           all(str2[i] == str1[i % g] for i in range(len(str2))):
            return str1[:g]
        return ""

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        int g = std::gcd((int)str1.size(), (int)str2.size());

        for (int i = 0; i < str1.size(); i++) {
            if (str1[i] != str1[i % g]) {
                return "";
            }
        }

        for (int i = 0; i < str2.size(); i++) {
            if (str2[i] != str1[i % g]) {
                return "";
            }
        }

        return str1.substr(0, g);
    }
};