LeetCode 1071: Greatest Common Divisor of Strings

Problem Restatement

We say string t divides string s if s is formed by concatenating t one or more times.

We are given two strings str1 and str2.

Return the largest string t that divides both str1 and str2.

The official constraints state that 1 <= str1.length, str2.length <= 1000.

Input and Output

Function shape:

def gcdOfStrings(str1: str, str2: str) -> str:
    ...

Examples

Example 1:

str1 = "ABCABC", str2 = "ABC"

"ABC" divides both: "ABCABC" = "ABC" * 2, "ABC" = "ABC" * 1.

Answer:

"ABC"

Example 2:

str1 = "ABABAB", str2 = "ABAB"

"AB" divides both.

Answer:

"AB"

Key Insight

If a string t divides both str1 and str2, then t also divides str1 + str2 and str2 + str1. So str1 + str2 == str2 + str1 is a necessary condition.

If this condition holds, the GCD divisor string has length gcd(len(str1), len(str2)).

Correctness

If str1 + str2 != str2 + str1, no common divisor exists (return "").

Otherwise, the largest divisor must have a length that divides both len(str1) and len(str2), so its length is gcd(len(str1), len(str2)).

Edge Cases

• Check the minimum input size allowed by the constraints.
• Verify duplicate values or tie cases if the input can contain them.
• Keep the return value aligned with the exact failure case in the statement.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from math import gcd

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

Testing

def run_tests():
    s = Solution()

    assert s.gcdOfStrings("ABCABC", "ABC") == "ABC"
    assert s.gcdOfStrings("ABABAB", "ABAB") == "AB"
    assert s.gcdOfStrings("LEET", "CODE") == ""
    assert s.gcdOfStrings("AA", "A") == "A"

    print("all tests passed")

run_tests()