Greatest Common Divisor of Strings

Difficulty: Easy

Problem

For two strings s and t, we say 't divides s' if s = t + t + ... + t (i.e., t is concatenated with itself one or more times to form s). Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Example

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
Explanation: "ABC" divides both "ABCABC" (repeated 2×) and "ABC" (repeated 1×). It is the largest such divisor.

Brute-force approach

Try all possible prefix lengths from longest to shortest. For each prefix, check if it divides both strings.

Steps

  1. Iterate candidate lengths from min(len1, len2) down to 1
  2. Skip lengths that don't divide both string lengths
  3. Extract the prefix candidate
  4. Check if repeating candidate matches both strings
  5. Return the first (longest) match, or empty string

Time complexity: O(min(n,m) × (n+m)) · Space complexity: O(n + m)

Trade-offs

  • Tries many candidate lengths
  • Builds repeated strings for each check — expensive
  • Doesn't leverage the mathematical GCD insight

Optimal approach

Key insight: If two strings share a common divisor pattern, then str1+str2 must equal str2+str1. The GCD string length is always gcd(len(str1), len(str2)).

Use the key mathematical insight: if str1+str2 == str2+str1, the GCD string is the prefix of length gcd(len(str1), len(str2)). Otherwise, no GCD exists.

Steps

  1. Check if str1 + str2 == str2 + str1
  2. If not equal, return empty string
  3. Compute gcd(len(str1), len(str2))
  4. Return str1[0 : gcdLen]

Time complexity: O(n + m) · Space complexity: O(n + m)