Sponsored
Sponsored
This approach leverages the mathematical concept of the Greatest Common Divisor (GCD) to determine the largest string that divides both given strings, str1 and str2.
First, check if str1 + str2 == str2 + str1. If not, that means there's no possible common divisor string. If they are equal, find the GCD of the lengths of the two strings. The prefix of this length is the required greatest common divisor string.
Time Complexity: O(N), where N is the sum of lengths of str1 and str2 due to equality check.
Space Complexity: O(1).
1def gcd_of_strings(str1, str2):
2 def gcd(a, b):
3 while b:
4 a, b = b, a % b
5 return a
6
7 if str1 + str2 != str2 + str1:
8 return ""
9 length = gcd(len(str1), len(str2))
10 return str1[:length]The function gcd_of_strings checks if str1 + str2 is equal to str2 + str1. If not, they don't have a common divisor string. If they do, it calculates the GCD of the lengths of the two strings and uses this GCD to slice the first string to obtain the longest common divisor string.
In this method, the idea is to iterate over possible substring lengths of the two input strings and check if these substrings can divide both strings. We start with the longest possible potential divisor, reducing the length until a valid divisor is found.
This is less efficient but straightforward when debugging or understanding the repetitive nature of string divisibility.
Time Complexity: O(N * M), where N and M are the lengths of str1 and str2.
Space Complexity: O(N + M) for storing temporary strings.
1public class Solution {
2 public string GcdOfStrings(string str1, string str2) {
3 int minLength = Math.Min(str1.Length, str2.Length);
4 for (int i = minLength; i > 0; i--) {
if (str1.Length % i == 0 && str2.Length % i == 0) {
string candidate = str1.Substring(0, i);
if (str1.Replace(candidate, "") == "" && str2.Replace(candidate, "") == "") {
return candidate;
}
}
}
return "";
}
}The C# solution tries all possible lengths starting from the smallest length of the given strings down to 1. For each possible divisor length, it checks if it evenly divides both strings, and then verifies if replacing that substring from both strings results in empty strings, confirming it as a valid divisor.