Problem Statement in English

You’re given two strings str1 and str2. Return the largest string x such that x divides both str1 and str2.

A string t divides string s if the string s can be formed by concatenating t multiple times.

Approach

Assuming str1 is the longer string, we can check if str1 can be formed by concatenating str2 multiple times. If it can, then str2 is a common divisor of both strings.

If not, then we need to check for all possible substrings of str2 that can be a common divisor of both str1 and str2.

If we still can’t find any common divisor, then we return an empty string.

This is a brute force approach, and results in a time complexity of $O(n^2)$, but it works for the given constraints. The canonical solution to this problem requires some more theory.

There is a property that if str1 and str2 have a common divisor, then the length of the greatest common divisor is simply the gcd of the lengths of str1 and str2. This divisor will only exist if the strings “commute” (i.e. str1 + str2 == str2 + str1). Otherwise, there is no common divisor, and we can return an empty string.

This brings our time complexity down to $O(n)$, where $n$ is the length of the longer string, since we only need to check if the two strings commute and then return the substring of the longer string up to the gcd of their lengths.

And we’re done!

Solution in Python

• Naive Solution, Time: $O(n^2)$, Space: $O(1)$

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if len(str1) < len(str2):
            str1, str2 = str2, str1

        N1 = len(str1)
        N2 = len(str2)

        if str1 == str2 * (N1 // N2):
            return str2

        res = ""

        for r in range(1, N2 + 1):
            x = str2[:r]
            NX = r
            
            if str1 == x * (N1 // NX) and str2 == x * (N2 // NX):
                res = max(res, x)

        return res

• Optimal Solution, Time: $O(n)$, Space: $O(1)$

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 == str2 + str1:
            d = gcd(len(str1), len(str2))

            return str1[:d]
        
        return ""

And we are done.

Mistakes I Made

I had to look up the optimal solution, but I was able to come up with the brute force solution on my own.