1071. Greatest Common Divisor of Strings - Explanation

Description

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).

You are given two strings str1 and str2, return the largest string x such that x divides both str1 and str2. If there is no such string, return "".

Example 1:

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

Output: "AB"

Example 2:

Input: str1 = "NANANA", str2 = "NANA"

Output: "NA"

Constraints:

1 <= str1.length, str2.length <= 1000
str1 and str2 consist of English uppercase letters.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Iteration

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

        def isDivisor(l):
            if len1 % l != 0 or len2 % l != 0:
                return False
            f1, f2 = len1 // l, len2 // l
            return str1[:l] * f1 == str1 and str1[:l] * f2 == str2

        for l in range(min(len1, len2), 0, -1):
            if isDivisor(l):
                return str1[:l]

        return ""

Time & Space Complexity

Time complexity: $O(min(m, n) * (m + n))$
Space complexity: $O(m + n)$

Where $m$ and $n$ are the lengths of the strings $str1$ and $str2$ respectively.

2. Iteration (Space Optimized)

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

        for l in range(n, 0, -1):
            if m % l != 0 or n % l != 0:
                continue

            valid = True
            for i in range(m):
                if str1[i] != str2[i % l]:
                    valid = False
                    break
            if not valid: continue

            for i in range(l, n):
                if str2[i] != str2[i % l]:
                    valid = False
                    break
            if valid: return str2[:l]

        return ""

Time & Space Complexity

Time complexity: $O(min(m, n) * (m + n))$
Space complexity: $O(g)$ for the output string.

Where $m$ is the length of the string $str1$ , $n$ is the length of the string $str2$ , and $g$ is the length of the output string.

3. Greatest Common Divisor

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""

        g = gcd(len(str1), len(str2))
        return str1[:g]

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(m + n)$ .

Where $m$ and $n$ are the lengths of the strings $str1$ and $str2$ respectively.

4. Greatest Common Divisor (Space Optimized)

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

        if all(str1[i] == str1[i % g] for i in range(len(str1))) and \
           all(str2[i] == str1[i % g] for i in range(len(str2))):
            return str1[:g]
        return ""

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(g)$ for the output string.

Where $m$ is the length of the string $str1$ , $n$ is the length of the string $str2$ , and $g$ is the GCD of $m$ and $n$ .