Problem: 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.
Example:
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
Input: str1 = "LEET", str2 = "CODE"
Output: ""
Approach: A simple approach would be to check for every prefix of the smaller string and check if the prefix is such that
prefix + prefix + prefix + ... + prefix = str1
prefix + prefix + prefix + ... + prefix = str2
We can do some optimization like choosing a prefix such that the length of prefix is divisor of lengths of both str1 and str2 and may be more but whatever optimization we will do the complexity is going to be on higher side i.e. O(m^2 + n^2).
Let's try to see problem from different view, sometimes looking at the examples really help. If you see closely, you can find GCD of str1 and str2 can exist only if
str1 + str2 = str2 + str1
Why? Let's say GCD of both strings is gcd then:
str1 = gcd + gcd + gcd + ... m times
str2 = gcd + gcd + gcd + ... n times
str1 + str2 = gcd + gcd + gcd + ... (m + n) times
str2 + str1 = gcd + gcd + gcd + ... (n + m) times
so you see str1 + str2 is equal to str2 + str1.
Now that we know when GCD exist, what is GCD of both strings? Just look at the example closely and you will quickly find that GCD is the prefix of length of GCD(Length(str1), Length(str2).
That's all!
Implementation in C#:
Brute-force:
public string GcdOfStrings(string str1, string str2)
{
string gcd = string.Empty;
int str1Len = str1.Length;
int str2Len = str2.Length;
int minStrLen = Math.Min(str1Len, str2Len);
int currLen = 1;
if (!string.IsNullOrEmpty(str1) && !string.IsNullOrEmpty(str2))
{
while (currLen <= minStrLen)
{
if (str1Len % currLen == 0 && str2Len % currLen == 0)
{
string prefix = str1.Substring(0, currLen);
if (str2.StartsWith(prefix))
{
if (this.isStrRepetitionOfPrefix(str1, prefix)
&& this.isStrRepetitionOfPrefix(str2, prefix))
{
gcd = prefix;
}
}
}
++currLen;
}
}
return gcd;
}
private bool isStrRepetitionOfPrefix(string str, string prefix)
{
int i = prefix.Length;
while(i < str.Length)
{
if (str.Substring(i, prefix.Length) != prefix)
{
return false;
}
i += prefix.Length;
}
return true;
}
Optimized:
public string GcdOfStrings(string str1, string str2)
{
if (str1 + str2 != str2 + str1)
{
return string.Empty;
}
int maxLength = str1.Length;
int minLength = str2.Length;
if (maxLength < minLength)
{
minLength = maxLength;
maxLength = str2.Length;
}
int gcdLength = this.getGCD(maxLength, minLength);
return str1.Substring(0, gcdLength);
}
private int getGCD(int a, int b)
{
while (b != 0)
{
int temp = b;
b = a % b;
a = temp;
}
return a;
}
Complexity: Solution 1: O(m^2 + n^2)
Solution 2: O(m + n)
