Solution 1 - GCD of Lengths (Optimal)

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2. A string t divides s if s is formed by concatenating t one or more times. The key insight is: if a common divisor string exists, then str1 + str2 == str2 + str1. The length of the GCD string equals gcd(len(str1), len(str2)).

TimeComplexity: O(m + n)

SpaceComplexity: O(m + n)

""" 1071.1 - Solution 1 - GCD of Lengths (Optimal) """

#####################################################################################
# Imports
#####################################################################################
from math import gcd

#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def gcdOfStrings(self, str1: str, str2: str) -> str:
        """Greatest Common Divisor of Strings Function"""
        if str1 + str2 != str2 + str1:
            return ""
        return str1[:gcd(len(str1), len(str2))]


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().gcdOfStrings("ABCABC", "ABC"))        # "ABC"
    print(Solution().gcdOfStrings("ABABAB", "ABAB"))        # "AB"
    print(Solution().gcdOfStrings("LEET", "CODE"))          # ""


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Brute Force Check All Prefixes

Try every possible prefix of str1 from longest to shortest. For each prefix, check if its length divides both string lengths and if repeating the prefix reconstructs both strings. Return the first (longest) valid prefix.

TimeComplexity: O(min(m, n) \cdot (m + n))

SpaceComplexity: O(min(m, n))

""" 1071.2 - Solution 2 - Brute Force Check All Prefixes """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def gcdOfStrings(self, str1: str, str2: str) -> str:
        """Greatest Common Divisor of Strings Function"""
        for i in range(min(len(str1), len(str2)), 0, -1):
            if len(str1) % i == 0 and len(str2) % i == 0:
                candidate = str1[:i]
                if candidate * (len(str1) // i) == str1 and candidate * (len(str2) // i) == str2:
                    return candidate
        return ""


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().gcdOfStrings("ABCABC", "ABC"))        # "ABC"
    print(Solution().gcdOfStrings("ABABAB", "ABAB"))        # "AB"
    print(Solution().gcdOfStrings("LEET", "CODE"))          # ""


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

1071 - Greatest Common Divisor of Strings

Solution 1 - GCD of Lengths (Optimal)

Solution 2 - Brute Force Check All Prefixes