Tag: GCD

Difficulty: Easy
Topics: Math, String

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.

I initially solved this like this:

string gcdOfStrings(string str1, string str2) {
        int minlen = min(str1.size(), str2.size());
        // check if one is substring of another. if not, return "".
        if (str1.substr(0, minlen) != str2.substr(0, minlen)) {
                return "";
        }
        for (int i = minlen; i > 0; i--) {
            // if str1 and str2 are not divisible by i, pass
            if (! (str1.size() % i == 0 && str2.size() % i == 0)) {
                continue;
            }
            // check if GCD is correct
            string GCD = str1.substr(0, i);
            for (int j = 0; j < str1.size(); j+=i) {
                if (GCD != str1.substr(j, i)) goto pass;
            }
            for (int j = 0; j < str2.size(); j+=i) {
                if (GCD != str2.substr(j, i)) goto pass;
            }
            return GCD;
            pass: ;
        }
        return "";
    }

But there was a simpler logic:

str1 and str2 have a gcd iff str1+str2 == str2+str1

Proof:
str1 = m (GCD)
str2 = n (GCD)
str1 + str2 = (m + n) GCD = str2 + st1

if they have a gcd, find it with math -> gcd().

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