1071.Greatest_Common_Divisor_of_Strings(Easy).md

1071. Greatest Common Divisor of Strings (Easy)

Date and Time: Sep 13, 2024, 22:00 (EST)

Link: https://leetcode.com/problems/greatest-common-divisor-of-strings/

Question:

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

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Example 2:

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

Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Constraints:

• 1 <= str1.length, str2.length <= 1000

• str1 and str2 consist of English uppercase letters.

Walk-through:

1. We can loop over the min(len(str1), len(str2)) backward because we want to find the largest string prefix, and we slice a prefix from str1 or str2, then we first compare if the length of this prefix is divisible by str1 and str2, so we know this prefix can concatenate these two strings.

2. If we find a prefix, we then use this prefix from either str1 or str2 (not both) and compare if we multiply the same prefix multiple times, can we get the original str1 and str2 back. If so, we can return the prefix str1[:i], because we start backward, which will be the largest string. Otherwise, we return "" in the end.

Date time: Apr 5, 2026, 24m 49s

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # str1 = "abab", str2 = "ab"
        # str1 = "abababab", str2 = "abab"
        # str1= "ab", str2 = "abab"
        # str1 = "abc", str2 = "def"
        # res = "", num = 0

        # maintain two ptrs (i, j) for str1 and str2, while loop to make sure we are still in bound
        # Detemine GCD: If res * (len(str1) // x) == str1 and res * (len(str2) // x) == str2, update res
        # TC: O(n^2), n=max(len(str1), len(str2)) SC: O(n)

        # i, j = 3, 3
        # res = "abab"
        res = ""
        i, j = 0, 0
        while i < len(str1) and j < len(str2):
            # Check if two chars are the same
            if str1[i] == str2[j]:
                # Check if substring str1[:i] is valid for both strings
                substring = str1[:i+1]
                if (substring * (len(str1) // len(substring))) == str1 and (substring * (len(str2) // len(substring))) == str2:
                    res = substring
            i, j = i+1, j+1
        return res

Python Solution:

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        # Try a prefix and then time its muliplication and see if it matches
        # From the back so we know the largest string
        for i in range(min(len(str1), len(str2)), 0, -1):
            if len(str1) % len(str1[:i]) == 0 and len(str2) % len(str2[:i]) == 0:
                if str1[:i] * (len(str1) // i) == str1 and str1[:i] * (len(str2) // i) == str2:
                    return str1[:i]
        return ""

Time Complexity: $O(min(m, n)* (n+m))$, m is length of str1, n is length of str2.
Space Complexity: $O(1)$