Greatest Common Divisor of Strings

lcpy gen -n 1071   # by problem number
lcpy gen -s gcd_of_strings   # by problem name

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

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

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

from math import gcd


class Solution:
    # Time: O(n + m) — concatenate + compare strings of total length n + m
    # Space: O(n + m) — concatenated strings
    def gcd_of_strings(self, str1: str, str2: str) -> str:
        # If a common divisor exists, str1 and str2 must compose the same
        # string regardless of concatenation order.
        if str1 + str2 != str2 + str1:
            return ""

        # The largest common divisor has length = gcd of the two lengths.
        gcd_len = gcd(len(str1), len(str2))
        return str1[:gcd_len]