Greatest Common Divisor of Strings — Solution

Problem

Given two strings, find the largest string that "divides" both — meaning each string is formed entirely by repeating that smaller string some number of times. For instance, "AB" divides "ABABAB" because "ABABAB" = "AB" + "AB" + "AB".

Example:

• Input: str1 = "ABABAB", str2 = "ABAB"
• Output: "AB"
• Explanation: "AB" divides both strings (str1 = AB×3, str2 = AB×2)

Counter-example (no common divisor):

• Input: str1 = "LEET", str2 = "CODE"
• Output: ""
• Explanation: No string divides both, because they share no repeated structure

Intuition

If a common divisor exists, both strings are just repetitions of the same base unit. This means assembling them in either order must produce the same result: str1 + str2 must equal str2 + str1. Once that property holds, the longest such base unit has length equal to the GCD of the two string lengths — because if str1 repeats the base m times and str2 repeats it n times, the base length divides both lengths, and the greatest such divisor gives the longest base.

Solution — GCD of Lengths

Check whether str1 + str2 equals str2 + str1. If not, no common divisor exists. Otherwise, the answer is the prefix of str1 with length gcd(len(str1), len(str2)).

1. Concatenate str1 + str2 and str2 + str1; if they differ, return "".
2. Compute common_length = gcd(len(str1), len(str2)).
3. Return str1[:common_length].

1from math import gcd
2
3class Solution:
4    def gcdOfStrings(self, str1: str, str2: str) -> str:
5        # A common divisor can only exist if the strings are interchangeable by concatenation order
6        if str1 + str2 != str2 + str1:
7            return ""
8        common_length = gcd(len(str1), len(str2))
9        return str1[:common_length]

Time: O(m + n) — dominated by the string concatenation comparison, where m and n are the lengths of str1 and str2.

Space: O(m + n) — the two concatenated strings each have length m + n.

Complexity Summary

Common Mistakes

• Skipping the concatenation check — without verifying str1 + str2 == str2 + str1, you might return a wrong prefix for inputs that share no common divisor (e.g. returning "L" for "LEET" and "CODE").
• Checking prefix divisibility in a loop — iterating through all prefix lengths and testing each one is O(n²); the GCD property makes this unnecessary.
• Using gcd on character frequencies instead of string lengths — the relevant GCD is between the repeat counts, which maps directly to string lengths, not individual character counts.
• Returning str1[:gcd_len - 1] — the GCD length gives exactly the right slice; subtracting one yields a shorter string that may not even divide the inputs.

Related Problems

• longest-common-prefix — finds the longest shared prefix among an array of strings, a related structural comparison
• valid-anagram — checks a string-level property by comparing character distributions
• is-subsequence — another form of "does string A appear inside string B" with a structural constraint
• isomorphic-strings — determines whether two strings share the same repeating pattern structure
• find-the-index-of-the-first-occurrence-in-a-string — locating a pattern string within a longer string