Problem Statement 1071. Greatest Common Divisor of Strings

For two strings s and t, we say "t divides s" if and only if s = t t t ... 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.

My Thought Process

Even though the leetcode marked it as an Easy problem, I must admit I found it difficult to immediately come up with a solution.

Let me review the test cases provided by leetcode and go over them to explain my confusion.

Test Cases

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

From the problem statement and test case 1, I did determine that we need to output the largest string("ABC") concatenating which we can get both strings. (default string "ABC" === str2 and "ABC" "ABC" === str1).

However, looking at test case 2 I quickly realized that my understanding was not correct as according to that I should output "ABAB" as that is the longest string using which I can create both the strings. But I jumped to code and started to map out a solution. (Rookie mistake?)

What Failed/Succeeded

I was only able to map out a solution where:

1. find the GCD of two strings.
2. iterate from the length of the smallest string to GCD
3. take a substring from the smallest string to the current iteration value.
4. if both the strings contain that substring return that substring as the answer.
5. if no string is found return "".

As you can see my solution failed for the strings where str1 contains str2 but also contains some other additional characters. violating the requirement that s = t t ... t t.

I had to turn to neetcode's solution for help. I quickly understood my issues:

1. I was finding the GCD of the length of the string, NOT the string itself. I need to find a string where repeating those strings I can create both the strings without any remaining characters.

2. I realized why "ABAB" can not be the answer for test case 2:

• we need to find x such that it divides both the strings equally. so taking "ABAB" as the string you can create str2 completely but for str1 you end up with "ABABABAB". You end up with 2 excess "AB" and can not say that you created str1 completely by combining x.

• "ABAB" length 4 and "ABABAB" length 6. The GCD of the 2 strings = 2. Hence the output needs to be a string of length 2.

Output

Time and Space complexity

Time Complexity: In the worst case we iterate over the Min(str1,str2) and we need to recreate str1 and str2 so that will be (str1.length str2.length) so overall time complexity will be O(min(str1,str2) * (str1.length str2.length))

Space Complexity: O(1) as we do not need any additional space.