JavaScript Algorithm: Solving Greatest Common Divisor with Euclidean Algorithm

https://leetcode.com/problems/greatest-common-divisor-of-strings

Problem Overview

Given two strings str1 and str2, we want to find the largest string x such that x divides both str1 and str2. Here, "string t divides string s" means s is made by concatenating t one or more times (e.g., s = t + t + ... + t).

Examples

Input: str1 = “ABCABC”, str2 = “ABC” Output: “ABC”

Input: str1 = “ABABAB”, str2 = “ABAB” Output: “AB”

Input: str1 = “LEET”, str2 = “CODE” Output: “”

Understanding the Core Idea: Greatest Common Divisor (GCD)

This problem parallels the concept of the Greatest Common Divisor (GCD) of two numbers:

• The GCD of two integers is the largest number that divides both without a remainder.
• For example, GCD(12, 8) = 4, since 4 is the largest number dividing both 12 and 8.

Similarly, for strings:

• The largest string x that divides both str1 and str2 must be a substring repeated multiple times to form both strings.
• The length of x must divide both str1.length and str2.length.

What is the Euclidean Algorithm?

To find the GCD of two numbers efficiently, we use the Euclidean algorithm, which relies on this principle

const gcd = (a, b) => b === 0 ? a : gcd(b, a % b);

const str1 = "ABABAB";
const str2 = "ABAB";

const len = gcd(str1.length, str2.length); // gcd(6, 4) = 2

const result = str1.slice(0, len); // "AB"

• % is the modulo operator (remainder).
• Repeat this process until the remainder is zero.
• When the remainder is zero, the other number is the GCD.

Early Return: Verifying If Common Divisor Exists

Before computing the GCD and slicing strings, we must verify whether a common repeated substring exists at all.

str1 + str2 === str2 + str1

• If true, str1 and str2 share a common repeating pattern.
• If false, no such common substring exists → return "" immediately.

Complete Code Implementation

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function(str1, str2) {
    if (str1+str2 !== str2+str1) return "";

    const gcd = (a,b) => b === 0 ? a : gcd(b, a%b);
    const length = gcd(str1.length, str2.length);

    return str1.slice(0, length);
};

Summary

• This problem transforms into finding the greatest common divisor of string lengths with respect to repeated substrings.
• Use the Euclidean algorithm for fast GCD calculation.
• Check the early return condition to confirm that a common repeated pattern exists.
• Return the substring of length equal to the GCD from the start of either string.