1071. Greatest Common Divisor of Strings - Explanation

Problem Link

Description

For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + t + t (i.e., t is concatenated with itself one or more times).

You are given two strings str1 and str2, return the largest string x such that x divides both str1 and str2. If there is no such string, return "".

Example 1:

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

Output: "AB"

Example 2:

Input: str1 = "NANANA", str2 = "NANA"

Output: "NA"

Constraints:

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Iteration

Intuition

A string t divides both str1 and str2 only if its length divides both string lengths and repeating t the appropriate number of times reconstructs each string. We search for the longest such divisor by checking all possible lengths from the minimum length down to 1.

Algorithm

1. For each possible length l from min(len1, len2) down to 1:
   • Check if l divides both len1 and len2.
   • Extract the prefix str1[:l] as the candidate divisor.
   • Check if repeating this prefix len1/l times equals str1 and len2/l times equals str2.
2. Return the first valid prefix found.
3. If no valid divisor exists, return an empty string.

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

        def isDivisor(l):
            if len1 % l != 0 or len2 % l != 0:
                return False
            f1, f2 = len1 // l, len2 // l
            return str1[:l] * f1 == str1 and str1[:l] * f2 == str2

        for l in range(min(len1, len2), 0, -1):
            if isDivisor(l):
                return str1[:l]

        return ""

Time & Space Complexity

• Time complexity: $O(min(m, n) * (m + n))$
• Space complexity: $O(m + n)$

Where $m$ and $n$ are the lengths of the strings $str1$ and $str2$ respectively.

---

2. Iteration (Space Optimized)

Intuition

Instead of constructing repeated strings and comparing them (which uses extra space), we can validate a candidate divisor by checking character-by-character using modular indexing. Each character at position i should match the character at position i % l in the candidate prefix.

Algorithm

1. Ensure str1 is the longer string by swapping if necessary.
2. For each possible length l from n down to 1:
   • Check if l divides both lengths.
   • Verify that str1[i] == str2[i % l] for all positions in str1.
   • Verify that str2[i] == str2[i % l] for positions from l to n.
3. Return the prefix str2[:l] if all checks pass.
4. Return an empty string if no valid divisor exists.

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        if m < n:
            m, n = n, m
            str1, str2 = str2, str1

        for l in range(n, 0, -1):
            if m % l != 0 or n % l != 0:
                continue

            valid = True
            for i in range(m):
                if str1[i] != str2[i % l]:
                    valid = False
                    break
            if not valid: continue

            for i in range(l, n):
                if str2[i] != str2[i % l]:
                    valid = False
                    break
            if valid: return str2[:l]

        return ""

Time & Space Complexity

• Time complexity: $O(min(m, n) * (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 length of the output string.

---

3. Greatest Common Divisor

Intuition

If a common divisor string exists, then concatenating the two strings in either order must produce the same result: str1 + str2 == str2 + str1. This is because both strings are built from the same repeating pattern. Once verified, the GCD of the two string lengths gives us the length of the largest common divisor.

Algorithm

1. Check if str1 + str2 == str2 + str1. If not, return an empty string.
2. Compute g = gcd(len(str1), len(str2)).
3. Return the prefix str1[:g].

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""

        g = gcd(len(str1), len(str2))
        return str1[:g]

Time & Space Complexity

• Time complexity: $O(m + n)$
• Space complexity: $O(m + n)$.

Where $m$ and $n$ are the lengths of the strings $str1$ and $str2$ respectively.

---

4. Greatest Common Divisor (Space Optimized)

Intuition

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.

Algorithm

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.

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 ""

Time & Space 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$.

---

Common Pitfalls

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.