6Companies30days

1071. Greatest Common Divisor of Strings

Question

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

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

Solution

• to check if a string is divisible by another use (str1+str2 == str2+str1)
• Their gcd is essentially the gcd of their length

string gcdOfStrings(string str1, string str2) {     
    if( str1+str2 == str2+str1 ) {
        return str1.substr(0, __gcd(str1.size(), str2.size()) );
    }
    return "";       
}