# Luqman Shaban's Blog # 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);
}
``````

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