DEV Community

Luqman Shaban
Luqman Shaban

Posted on

Finding the Greatest Common Divisor of Strings in TypeScript

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);
}
Enter fullscreen mode Exit fullscreen mode

Explanation:

  • We start by defining the gcdOfStrings function, which takes two string parameters: str1 and str2.
  • We first check if the lengths 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);
}
Enter fullscreen mode Exit fullscreen mode

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"));
Enter fullscreen mode Exit fullscreen mode

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.

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.

Top comments (0)