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.
1function gcdOfStrings(str1, str2) {
2 var isDivisible = function(s, x) {
3 return s.split(x).join('') === '';
4 };
5 for (let i = Math.min(str1.length, str2.length); i > 0; i--) {
6 if (str1.length % i === 0 && str2.length % i === 0) {
7 let candidate = str1.substring(0, i);
8 if (isDivisible(str1, candidate) && isDivisible(str2, candidate)) {
9 return candidate;
10 }
11 }
12 }
13 return '';
14}In the JavaScript solution, we define a helper function isDivisible to check if a candidate string can evenly divide a given string. We then iterate over potential lengths starting with the shorter length downwards, checking for each whether it can serve as a valid divisor for both strings.