Greatest Common Divisor of Strings

Difficulty: Easy

Problem

Say a string t 'tiles' a string s when s is exactly t written out one or more times in a row. Given two strings str1 and str2, return the longest string x that tiles both of them.

Example

Input: str1 = "XYXYXY", str2 = "XYXY"
Output: "XY"
Explanation: "XY" repeats 3 times to make "XYXYXY" and 2 times to make "XYXY". "XYXY" cannot tile "XYXYXY" since 6 is not a multiple of 4, so "XY" is the longest.

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)

Pseudocode

function gcdOfStrings(str1, str2):
    if str1 + str2 != str2 + str1:
        return ""
    gcdLen = gcd(len(str1), len(str2))
    return str1[0:gcdLen]

Hints

  • If str1 + str2 != str2 + str1, no common divisor exists
  • The GCD string length must be gcd(len(str1), len(str2))
  • The answer is always a prefix of both strings

Complexity questions

What is the time complexity of the brute force approach (trying all prefix lengths)?

O(min(n,m) × (n+m)). Up to min(n,m) candidates, each verification costs O(n+m) for string repetition and comparison.

What is the time complexity of the optimal (concatenation check + GCD) approach?

O(n + m). O(n+m) for the concatenation check, plus O(log(min(n,m))) for GCD ≈ O(n+m).

Why does str1+str2 == str2+str1 guarantee a common divisor exists?

Because both strings are built by repeating the same base pattern. If concatenation is commutative, both strings must be multiples of the same base string t.

Check your understanding of Greatest Common Divisor of Strings

What does it mean for string t to 'divide' string s?

s can be formed by repeating t one or more times. t divides s means s = t + t + ... + t. For example, "AB" divides "ABABAB" (3 repetitions).

Given str1 = "ABABAB" and str2 = "ABAB", what is the GCD string?

"AB". "AB" divides "ABABAB" (3×) and "ABAB" (2×). gcd(6,4) = 2, and the first 2 chars = "AB".

When does NO common divisor exist?

When str1 + str2 != str2 + str1. If str1+str2 ≠ str2+str1, the strings don't share a common repeating pattern.

Related problems

Keep practising