Problem of The Day: Greatest Common Divisor of Strings

Problem Statement

leetcode problem link

Brute Force [Accepted]

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

        len1 = len(str1)
        len2 = len(str2)
        res_len = 0
        res = ""
        for i in range(len2):
            curr = str2[:i+1]
            curr_len = len(curr)
            x = len1 // curr_len
            y = len2 // curr_len
            new_str1 = curr * x
            new_str2 = curr * y
            if new_str1 == str1 and new_str2 == str2 and curr_len > res_len:
                res = curr
                res_len = curr_len

        return res

Editorial

Approach 1: Brute Force

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

        def valid(k):
            if len1 % k or len2 % k:
                return False
            n1, n2 = len1 // k, len2 // k
            base = str1[:k]
            return str1 == n1 * base and str2 == n2 * base

        for i in range(min(len1, len2), 0, -1):
            if valid(i):
                return str1[:i]
        return ""

Approach 2: Greatest Common Divisor

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # Check if they have non-zero GCD string.
        if str1 + str2 != str2 + str1:
            return ""

        # Get the GCD of the two lengths.
        max_length = gcd(len(str1), len(str2))
        return str1[:max_length]