
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
- Initialize an empty string
substr
to store potential GCD candidates. - Iterate over each character of
str1
and keep appending it tosubstr
. - For each
substr
, check if bothstr1
andstr2
can be formed by repeatingsubstr
: - Use string replacement methods to check if the entire string becomes empty when thesubstr
is removed. - If both strings are divisible by the current
substr
, update the result withsubstr
. - Continue the process until all possible substrings are tested.
- 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;
}