LeetCode 1071. Greatest Common Divisor of Strings

Dec 21, 2025

Intuition

  1. Compare str1 + str2 == str2 + str1 because if they are not equal there is no GCD of the two
  2. find the gcd of two lengths and find return the string of that length from the two

Optimal Solution

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

        def find_gcd(len1, len2):
            if len1 > len2:
                if len1 % len2 == 0:
                    return len2
            if len2 >= len1:
                if len2 % len1 == 0:
                    return len1

            for i in range(min(len1,len2)+1, 0,-1):
                if len1 % i == 0 and len2 % i == 0:
                    return i
        gcd = find_gcd(len(str1),len(str2))
        return str1[:gcd]

Time Complexity

Time Complexity O(N+M)

Space Complexity O(N+M)

Steve Jin