1071. Greatest Common Divisor of Strings

Description

The problem asks to find the greatest common divisor (GCD) of two strings. Given two strings, str1 and str2, the GCD of these strings is defined as the largest string X such that X can divide both str1 and str2. A string X divides another string Y if Y is constructed by concatenating X multiple times.

Intuition

The intuition behind solving this problem is similar to finding the GCD of two numbers. We start by identifying the common prefix of the two strings and check if this prefix can be the GCD string. The potential GCD string must divide both strings without leaving any remainder.

Approach

1. Initialize an empty string substr to store potential GCD candidates.
2. Iterate over each character of str1 and keep appending it to substr.
3. For each substr, check if both str1 and str2 can be formed by repeating substr: - Use string replacement methods to check if the entire string becomes empty when the substr is removed.
4. If both strings are divisible by the current substr, update the result with substr.
5. Continue the process until all possible substrings are tested.
6. Return the largest valid substring that divides both strings.

Complexity

Time Complexity:

O(N * M), where N is the length of str1 and M is the length of str2. We potentially check each substring of str1 and replace it in both str1 and str2.

Space Complexity:

O(1) for the additional space used for the substring comparison, excluding the input strings.

Code

C++

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        string substr = "";
        string result = "";

        for (char i : str1) {
            string newstr1 = str1;
            string newstr2 = str2;
            substr += i;
            if (str1.find(substr) != string::npos) {
                if (replaceAll(newstr1, substr) == "" && replaceAll(newstr2, substr) == "") {
                    result = substr;
                }
            } else {
                return "";
            }
        }
        return result;
    }

private:
    string replaceAll(string str, string substr) {
        size_t pos;
        while ((pos = str.find(substr)) != string::npos) {
            str.erase(pos, substr.length());
        }
        return str;
    }
};

Python

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        substr = ""
        result = ""

        for i in str1:
            newstr1 = str1
            newstr2 = str2
            substr += i
            if str1.find(substr) != -1:
                if newstr1.replace(substr, "") == "" and newstr2.replace(substr, "") == "":
                    result = substr
            else:
                return ""
        return result

Java

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        String substr = "";
        String result = "";

        for (char i : str1.toCharArray()) {
            String newstr1 = str1;
            String newstr2 = str2;
            substr += i;
            if (str1.indexOf(substr) != -1) {
                if (newstr1.replaceAll(substr, "").equals("") && newstr2.replaceAll(substr, "").equals("")) {
                    result = substr;
                }
            } else {
                return "";
            }
        }
        return result;
    }
}

JavaScript

/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function (str1, str2) {
    let substr = "";
    let result = "";

    for (let i of str1) {
        let newstr = str1;
        newstr2 = str2;
        substr = substr + i;
        if (str1.indexOf(substr) !== -1) {
            if (newstr.replaceAll(substr, "") === "" && newstr2.replaceAll(substr, "") === "") {
                result = substr;
            }
        } else { return "" }
    } return result;
}