Problem
Given two strings str1 and str2, return the largest string that divides both strings. A string t divides another string s if s can be formed by concatenating t one or more times.If there is no common divisor string, return an empty string.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
str1 = "ABCABC"
str2 = "ABC"Output
"ABC"Solution
This solution uses the Greatest Common Divisor (GCD) of the lengths of the two strings. Before finding the GCD, we first check whether the two strings are made from the same repeating pattern.If
str1 + str2 is not equal to str2 + str1, the strings do not have a common divisor, so we return an empty string. If the concatenations are equal, both strings are constructed from the same repeating pattern. The length of the largest common divisor is the GCD of the two string lengths.
We then return the substring of str1 from index
0 to the GCD of the two lengths. The GCD itself is calculated using the Euclidean algorithm. The process repeatedly replaces
a and b with b and a % b until b becomes zero.
class Solution {
public String gcdOfStrings(String str1, String str2) {
if (!(str1 + str2).equals(str2 + str1))
return "";
return str1.substring(0, gcd(str1.length(), str2.length()));
}
public int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
}Complexity
The GCD calculation takesO(log(min(n, m))) time, where n and m are the lengths of the two strings.
We consider
O(log n) time complexity when the algorithm reduces the problem size by a constant factor at each step, usually by half.
The Euclidean algorithm repeatedly reduces the numbers using the remainder:
gcd(a, b) → gcd(b, a % b) → ...O(n + m) time.
Therefore, the overall time complexity is
O(n + m). The recursive GCD calculation uses O(log(min(n, m))) space due to the recursive call stack.