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).
1class Solution {
2 public String gcdOfStrings(String str1, String str2) {
3 if (!(str1 + str2).equals(str2 + str1)) {
4 return "";
5 }
6 return str1.substring(0, gcd(str1.length(), str2.length()));
7 }
8
9 private int gcd(int a, int b) {
10 while (b != 0) {
11 int temp = a % b;
12 a = b;
13 b = temp;
14 }
15 return a;
16 }
17}The Java solution follows the same logic, using a helper function gcd to calculate the GCD of the lengths of str1 and str2. If the combined strings are equal in both arrangements, it returns the substring of length equal to the GCD of the two lengths.
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--) {
5 if (str1.Length % i == 0 && str2.Length % i == 0) {
6 string candidate = str1.Substring(0, i);
7 if (str1.Replace(candidate, "") == "" && str2.Replace(candidate, "") == "") {
8 return candidate;
9 }
10 }
11 }
12 return "";
13 }
14}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.