LeetCode Challenge #1071. Greatest Common Divisor of Strings

Question 2 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #1071. Greatest Common Divisor of Strings

For two strings s and t, we say “t divides s” if and only if s = 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 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Constraints:

1 <= str1.length, str2.length <= 1000
str1 and str2 consist of English uppercase letters.

Video Solution

C++ Solution

				
					class Solution {
public:
    string gcdOfStrings(string str1, string str2) {

        if(str1+str2!=str2+str1)return "";

        int m=str1.size();
        int n=str2.size();

        string ans= str1.substr(0,gcd(m,n));

        return ans;

    }
};

Code Explanation

The purpose of this function is to find the greatest common divisor (GCD) of two input string “str1” and “str2” . It is the Greatest common divisor that completely divides two or more numbers without leaving any remainder.

Let’s see the approach step by step -:

Declared two string arguments ‘str1’ and ‘str2’ .
The first condition here checks if concatenating ‘str1’ and ‘str2’ together ( ‘str1’+ ’str2’ ) is equal to concatenating (‘str2’ +’str1’) . If these two concatenations are not equal , it means no common GCD exists between the two strings, and the function returns an empty string (‘ “ “ ‘) .
And if these two sums are equals to each other that means they have a GCD common in them .
Now we calculate the size of both strings , in order to find the size of resultant GCD. And stores them in ‘m’ and ‘n’ respectively. If we calculate the GCD of the size of both strings then it will be equal to the size of resultant GCD.
Then we are calling the ‘gcd’ function with arguments ‘m’ and ‘n’ .

Finally ‘substr’ function is used to extract a substring from ‘str1’ . This substring has the length equal to the GCD of the lenghths of ‘str1’ and ‘str2’.

The substring is stored in ‘ans’ variable, which is the GCD of two strings. And we will return the ‘ans’ string as the result of ‘ gcdOfStrings’ function.

Question 2 of 75 - LeetCode Weekly Challenge