Greatest Common Divisor of Strings

Problem

For two strings s and t, we say t divides s if s can be written as one or more back-to-back copies of t (that is, s = t + t + ... + t). Given strings str1 and str2, return the longest string x such that x divides both str1 and str2. If no such non-empty string exists, return "".

Examples

str1 = "ABCABC", str2 = "ABC" → "ABC" — "ABC" tiles str1 twice and str2 once.
str1 = "ABABAB", str2 = "ABAB" → "AB" — "AB" tiles both; the longer common prefix "ABAB" does not divide "ABABAB" because 6 is not a multiple of 4.
str1 = "LEET", str2 = "CODE" → "" — the strings share no common tiling unit.

Constraints

1 <= len(str1), len(str2) <= 1000
Both strings consist of uppercase English letters only.

Think about it first

Hint 1

Any string that divides `str1` is a prefix of `str1`, and its length must divide `len(str1)` exactly. The same holds for `str2`. So a common divisor's length divides both lengths.

Hint 2

The largest length that divides both `len(str1)` and `len(str2)` is `gcd(len(str1), len(str2))`. If any common divisor string exists at all, it is the prefix of that exact length.

Hint 3

There is a one-line test for whether a common divisor exists: `str1 + str2 == str2 + str1`. Two strings commute under concatenation only when both are repetitions of one common base string.

TL;DR

The answer is the prefix of length gcd(len1, len2) — and it exists iff str1 + str2 == str2 + str1. O(m + n) time, O(m + n) space.

Approach 1 — Brute force (try every candidate length)

Any dividing string is a prefix of str1, so scan candidate lengths from the shortest string down to 1. For each length, take that prefix and verify it tiles both strings exactly.

def gcdOfStrings(str1: str, str2: str) -> str:
    def divides(base: str, s: str) -> bool:
        if len(s) % len(base) != 0:
            return False
        return base * (len(s) // len(base)) == s

    shorter = min(len(str1), len(str2))
    for length in range(shorter, 0, -1):
        cand = str1[:length]
        if divides(cand, str1) and divides(cand, str2):
            return cand
    return ""

Complexity: O(min(m, n)) candidate lengths, each verified in O(m + n) → O(min(m, n) · (m + n)) time. For 1000-char inputs that is fine, but it does far more work than needed.

Approach 2 — GCD of lengths + commutativity test

The insight: if a common base string x exists, then both str1 and str2 are made of copies of x, so gluing them in either order produces the same run of x’s — meaning str1 + str2 == str2 + str1. Conversely, if that equality fails, no common base can exist. And when it holds, the longest base has length gcd(len(str1), len(str2)), because the base length must divide both lengths and we want the largest such divisor.

from math import gcd


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

gcd here is Euclid’s algorithm on the two lengths (not the strings): it repeatedly replaces the larger number by its remainder mod the smaller until one hits zero.

Walkthrough with str1 = "ABCABC", str2 = "ABC":

Commutativity: "ABCABC" + "ABC" = "ABCABCABC" and "ABC" + "ABCABC" = "ABCABCABC" — equal, so a common divisor exists.
gcd(6, 3) = 3, so the answer is str1[:3] = "ABC".

For str1 = "ABABAB", str2 = "ABAB": gcd(6, 4) = 2, and the strings commute, so the answer is "AB" — correctly rejecting the longer common prefix "ABAB".

Complexity: O(m + n) time (the concatenations dominate; the gcd is O(log) on the lengths), O(m + n) space for the concatenated strings.

Common pitfalls

Returning the full gcd-length prefix without the commutativity check — a shared prefix does not guarantee a shared tiling (e.g. "AABA" and "AA").
Taking gcd of the string contents instead of the two lengths.
Forgetting that an empty answer "" is a valid return when no common base exists.

Pattern takeaway

When one object is built by repeating another, questions about their “common unit” often reduce to number theory on their sizes: the common tiling length is the gcd of the individual lengths. A concatenation-commutativity check (a + b == b + a) is the clean existence test for “both are powers of one string.”