#1071 - Greatest Common Divisor of Strings

EasyArray / String

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2. A string t divides s if s can be formed by concatenating one or more copies of t.

Input	Output
str1 = "ABCABC", str2 = "ABC"	"ABC"
str1 = "ABABAB", str2 = "ABAB"	"AB"
str1 = "LEET", str2 = "CODE"	""

Solution Space

Try it

/**
 * Finds the largest string that divides both str1 and str2.
 * Key insight: if a GCD string exists, then str1 + str2 === str2 + str1.
 * Its length equals gcd(len1, len2).
 *
 * @param str1 First string (1 ≤ length ≤ 1000)
 * @param str2 Second string (1 ≤ length ≤ 1000)
 * @returns Largest common divisor string, or "" if none
 */
export function gcdOfStrings(str1: string, str2: string): string {
  // If concatenations in both orders differ, no common divisor exists
  if (str1 + str2 !== str2 + str1) return "";

  // The GCD string length mirrors numeric GCD of the two lengths
  return str1.slice(0, gcd(str1.length, str2.length));
}

function gcd(a: number, b: number): number {
  while (b) {
    [a, b] = [b, a % b];
  }
  return a;
}

Approach: concatenation check + numeric GCD – verify if str1 + str2 equals str2 + str1, then return the prefix of length gcd(str1.length, str2.length).

Time: O(n + m) – string concatenation/comparison dominates; GCD is O(log(min(n, m))).

Space: O(n + m) – for the concatenated strings used in the equality check.

Alternative approaches:

Approach	Idea	Time	Space
Brute-force divisor check	Try all prefixes of decreasing length, check if each divides both strings	O((n + m) · min(n, m))	O(min(n, m))

Why the concatenation + GCD method is preferred:

• It avoids repeatedly building and checking candidate strings.
• The concatenation equality is a clean necessary-and-sufficient condition, making the logic both optimal and easy to reason about.

#605 Can Place Flowers

#1431 Kids With the Greatest Number of Candies