Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Greatest Common Divisor of Strings

Problem (restated)

A string t divides s if s is t repeated some number of times. Given str1 and str2, return the largest t that divides both, or "" if none exists.

Intuition

If a common block exists, str1 + str2 equals str2 + str1 (they share the same period). The longest such block has length gcd(|str1|, |str2|) — Euclid on the lengths, then take that prefix.

Approaches

GCD of lengths

Unverified

Time O(n+m)Space O(n+m)

Idea. If str1+str2 !== str2+str1, return "". Else return str1.slice(0, gcd(len1, len2)).

Walkthrough. ABCABC, ABC → concat matches, gcd(6,3)=3 → ABC. LEET, CODE → concat differs → "".

Trade-offs. Concat is the O(n+m) check that avoids trial-dividing every prefix. The gcd itself is log of the lengths.

Solution

export function gcdOfStrings(str1: string, str2: string): string {
  if (str1 + str2 !== str2 + str1) return "";
  const gcd = (a: number, b: number): number => {
    while (b) { const t = a % b; a = b; b = t; }
    return a;
  };
  return str1.slice(0, gcd(str1.length, str2.length));
}

export function gcdOfStrings(str1: string, str2: string): string {
  if (str1 + str2 !== str2 + str1) return "";
  const gcd = (a: number, b: number): number => {
    while (b) { const t = a % b; a = b; b = t; }
    return a;
  };
  return str1.slice(0, gcd(str1.length, str2.length));
}

Template connection

GCD / LCM shape of Math & Number Theory: Euclid on lengths, then the prefix is the string gcd. Same gcd(b, a % b) as LC 365.

Reflection

If str1 + str2 differs from str2 + str1, there is no common divisor string. Otherwise the answer is the prefix whose length is gcd of the two lengths.
That prefix must tile both strings. When the gcd of the lengths is 1, the answer is at most one character, as with aaa and aa.
Two equal strings answer themselves. If one string is a repetition of the other, the answer is the shorter one.