How to Compute the Greatest Common Divisor of Strings?

For strings S and T, we say “T divides S” if and only if S = T + … + T (T concatenated with itself 1 or more times) Return the largest string X such that X divides str1 and X divides 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: “”

Note:

• 1 <= str1.length <= 1000
• 1 <= str2.length <= 1000
• str1[i] and str2[i] are English uppercase letters.

GCD of Strings Algorithms

Let’s review the GCD algorithm for two integers, which can be illustrated in the following C++ algorithm.

1
2
3
4

int gcd(int a, int b) { 
   if (b == 0) return a; 
   return gcd(b, a % b);  
} 

int gcd(int a, int b) { 
   if (b == 0) return a; 
   return gcd(b, a % b);  
} 

A bit similar, we need to check the terminating conditions that we can get the GCD directly. Otherwise, we need to make the longer string shorter by taking off the other string from the start. Then, the problem becomes a smaller problem, which can be recursively solved.

The first version of the recursive GCD algorithm for two strings in C++ as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1 == str2) {
            return str1;
        }
        if ((str1.find(str2) == string::npos) && (str2.find(str1) == string::npos)) {
            return "";
        }        
        if (str1.size() > str2.size()) {
            str1 = str1.substr(str2.size());
        }
        if (str2.size() > str1.size()) {
            str2 = str2.substr(str1.size());
        }
        return gcdOfStrings(str1, str2);
    }
};

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1 == str2) {
            return str1;
        }
        if ((str1.find(str2) == string::npos) && (str2.find(str1) == string::npos)) {
            return "";
        }        
        if (str1.size() > str2.size()) {
            str1 = str1.substr(str2.size());
        }
        if (str2.size() > str1.size()) {
            str2 = str2.substr(str1.size());
        }
        return gcdOfStrings(str1, str2);
    }
};

We also notice that if both strings do not contain each other, we can rewrite the string.find using a simpler logic:

1
2
3

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

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

For example, “123” + “123ABC” != “123ABC” + “123” and “ABC” + “ABCABC” == “ABCABC” + “ABC”. As the above recursion can be optimised using tail-recursion techniques, which can be converted to iterative while-loop.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        while (true) {
            if (str1 + str2 != str2 + str1) {
                return "";
            }
            if (str1 == str2) {
                return str1;
            }
            if (str1.size() > str2.size()) {
                str1 = str1.substr(str2.size());
            }
            if (str2.size() > str1.size()) {
                str2 = str2.substr(str1.size());
            }
        }
        return ""; // make compiler happy
    }
};

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        while (true) {
            if (str1 + str2 != str2 + str1) {
                return "";
            }
            if (str1 == str2) {
                return str1;
            }
            if (str1.size() > str2.size()) {
                str1 = str1.substr(str2.size());
            }
            if (str2.size() > str1.size()) {
                str2 = str2.substr(str1.size());
            }
        }
        return ""; // make compiler happy
    }
};

The space complexity is O(1) constant, and the time complexity is O(M/N) where M is the length of the longer string and N is the shorter length e.g. “A”, and “AAAAAAA…”

See also: Teaching Kids Programming – Greatest Common Divisor of Strings

–EOF (The Ultimate Computing & Technology Blog) —