Greatest Common Divisor of Strings

For two strings s and t. We say t divides s if and only $ s = t + 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 boths str1 and str2.

Example:

1 2	Input: str1 = "ABABC", str2 = "ABC" Ouput: "ABC"

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

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

Constraints:

$ 1 len_{str1}, len_{str2} $
str1 and str2 consist of English uppercase letters.

Solution

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        return (str1 + str2 == str2 + str1) ?
                str1.substr(0, gcd(size(str1), size(str2))) : "";
    }
};

Explanation: For two strings, if they are consisted by the same substrings (or same ingradient), their combination in opposite order should be the same. For example, is string A is ababab, string b is abab, it’s obvious that they have the same ingradient ab, so let’s combine them as $ a + b $ and $ b + a $, their results should be same. So, after we make sure that both two strings are made of the same ingradient, we can use gcd to find their greatest common division.

Proof: Assume str₁ = nX and str₂ = mX where X represents the common divisor of these two strings. Thus, the concatenated string str₁ + str₂ equals (n + m)X. We get substring of length gcd(len₁, len₂), if this length equals the size of str₂, which means the size of str₂ is divisible by str₁, any division should be equal when divised by gcd(str₁, str₂). The core is that str₁ + str₂ = str₂ + str₁.

General Solution:

class Solution {
    bool check(string t, string s) {
        int lenx = (int)s.length() / (int)t.length();
        string ans = "";
        for (int i = 0; i < lenx; i++) {
            ans = ans + t;
        }
        return ans == s;
    }
public:
    string gcdOfStrings(string str1, string str2) {
        int len1 = (int)str1.length(), len2 = (int)str2.length();
        for (int i = min(len1, len2); i >= 1; i--) {
            if (len1 % i == 0 && len2 % i == 0) {
                string X = str1.substr(0, i);
                if (check(X, str1) && check(X, str2)) return X;
            }
        }
        return "";
    }
}