Luqman Shaban's Blog
Finding the Greatest Common Divisor of Strings in TypeScript

Finding the Greatest Common Divisor of Strings in TypeScript

Luqman Shaban's photo
Luqman Shaban
·

3 min read

Introduction: In this article, we'll explore a TypeScript solution for finding the greatest common divisor (GCD) of two strings. The GCD of strings is defined as the longest common prefix of the two strings. We will break down the solution step by step and explain the code in detail.

Step 1: Defining the gcdOfStrings Function

function gcdOfStrings(str1: string, str2: string): string {
    if (str1 + str2 !== str2 + str1) {
        return "";
    }

    const gcdLength = gcd(str1.length, str2.length);
    return str1.substring(0, gcdLength);
}

Explanation:

  • We start by defining the gcdOfStrings function, which takes two string parameters: str1 and str2.

  • We first check if the sum of str1 and str2 are not equal. If they are not equal, it means that there cannot be a common divisor, so the function returns an empty string "".

  • Next, we calculate the GCD of the lengths of str1 and str2 using the gcd function, and store the result in the gcdLength variable.

  • Finally, we return a substring of str1 starting from index 0 and ending at gcdLength - 1. This is the common prefix of the two strings with a length equal to the GCD of their lengths.

Step 2: Implementing the gcd Helper Function

function gcd(a: number, b: number) {
    if (b === 0) {
        return a;
    }
    return gcd(b, a % b);
}

Explanation:

  • We define a helper function called gcd, which is responsible for calculating the GCD of two numbers, a and b, using the Euclidean algorithm.

  • The base case of the recursion is when b is equal to 0. In this case, we have found the GCD, and we return a.

  • If b is not equal to 0, we calculate the remainder of a divided by b using the modulo operator (a % b). This remainder becomes the new value of a, and b becomes the new value of b.

  • The function then recursively calls itself with the new values of a and b. This process continues until b becomes 0, at which point the GCD is found and returned.

Step 3: Testing the Solution

console.log(gcdOfStrings("ABCABBC", "ABC"));

Explanation:

  • To test our solution, we call the gcdOfStrings function with the strings "ABCABBC" and "ABC".

  • Since the lengths of these strings are 7 and 3, respectively, the GCD of their lengths is 1.

  • Therefore, the function returns a substring of "ABCABBC" starting from index 0 and ending at index 0, which is just "A".

  • The result is logged to the console, and you will see "A" as the output.

Here's the entire code: 

function gcdOfStrings(str1: string, str2: string): string {
   if(str1 + str2 !== str2 + str1) {
       return ""
   }

   const gcdLength = gcd(str1.length, str2.length)
   return str1.substring(0, gcdLength)
};

function gcd(a: number, b: number): number {
    if(b === 0){
        return a;
    }
    return gcd(b, a%b)
}

Conclusion:

In this article, we have walked through a TypeScript solution for finding the greatest common divisor (GCD) of two strings. We explained the code step by step, including the gcdOfStrings function and the helper gcd function, and demonstrated how to use the solution with a test case. This approach allows you to efficiently find the common prefix of two strings by leveraging the GCD of their lengths.

Let's Connect

datastructureleetcodeStringsTypeScriptDSA