GCD of Strings

LC75 #2

It’s day two of doing a programming puzzle everyday and today we’re attempting LC75 #2. Here’s the problem statement

For two strings s and t, we say "t divides s" if and only if s = t + t + t + ... + t + t (i.e., t is concatenated with itself one or more times).

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"

The elegant solutions are always the most satisfying. For a problem that sounds like it requires complex string manipulation loops, the actual key is a surprisingly simple property and a bit of classic number theory.

The trick? If two strings, str1 and str2, share a common repeating divisor string, then str1 + str2 must equal str2 + str1. If they aren't equal, no solution exists. This check is the foundation of an efficient and clean solution. This property arises because if str1 is k copies of a base string x and str2 is j copies, then both concatenations simply result in k+j copies of x.

---

Problem Deconstruction

The goal is to find the largest string x that can be concatenated with itself one or more times to form both str1 and str2.

• str1 = "ABCABCABC" is divisible by x = "ABC".

• str2 = "ABCABC" is divisible by x = "ABC".

• "ABC" is the largest such string.

If str1 = "LEET" and str2 = "CODE", no such x exists. Notice here that "LEETCODE" !== "CODELEET". The initial check holds.

---

The Mathematical Connection

This isn't just a string problem; it's a structural one. If a solution string x of length k exists, it must evenly "tile" both str1 (length n) and str2 (length m). This implies that k must be a mathematical divisor of both n and m.

To find the largest possible x, we need the largest possible k. This is simply the Greatest Common Divisor (GCD) of the two string lengths.

The algorithm relies on an ancient piece of tech: the Euclidean algorithm, which has been the gold standard for finding the GCD of two integers for over two millennia.

---

The Algorithm

1. Check for Existence: First, confirm that a common divisor structure is even possible. If str1 + str2 !== str2 + str1, return an empty string. There's no way to form both strings from a common base unit.

2. Find the Length: If the check passes, a solution is guaranteed. The length of the largest possible base string x will be GCD(str1.length, str2.length).

3. Extract the Result: The result is simply the prefix of either string with that calculated GCD length. For example, str1.substring(0, gcdLength).

---

JavaScript Implementation

First, a standard helper for the Euclidean algorithm.

JavaScript

/**
 * Calculates the Greatest Common Divisor of two numbers using the Euclidean algorithm.
 * @param {number} a
 * @param {number} b
 * @returns {number}
 */
const gcd = (a, b) => {
  if (b === 0) {
    return a;
  }
  return gcd(b, a % b);
};

Now, the main function integrates the logic.

JavaScript

/**
 * Finds the largest string x that divides both str1 and str2.
 * @param {string} str1
 * @param {string} str2
 * @returns {string}
 */
const gcdOfStrings = (str1, str2) => {
  // Step 1: Check if a common divisor structure exists.
  if (str1 + str2 !== str2 + str1) {
    return "";
  }

  // Step 2: Find the length of the potential GCD string.
  const gcdLength = gcd(str1.length, str2.length);

  // Step 3: Extract and return the substring.
  return str1.substring(0, gcdLength);
};

Example Usage

JavaScript

const str1 = "ABCABC";
const str2 = "ABC";
console.log(gcdOfStrings(str1, str2)); // Output: "ABC"

const str3 = "ABABAB";
const str4 = "ABAB";
console.log(gcdOfStrings(str3, str4)); // Output: "AB"

const str5 = "LEET";
const str6 = "CODE";
console.log(gcdOfStrings(str5, str6)); // Output: ""

---

Conclusion

This solution sidesteps brute-force iteration and pattern matching entirely. By identifying the underlying mathematical structure, the problem reduces to two simple, proven steps: a string concatenation check and a call to a classic GCD function. It's a testament to how recognizing a deeper principle can drastically simplify code.