"""
Greatest Common Divisor of Strings
    For two strings s and t, we say that t divides s
    if and only if s can be formed by concatenating
    t 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. If no such string exists, return "".

Example 1
    Input: str1 = "ABAB", str2 = "AB"
    Output: "AB"

Example 2
    Input: str1 = "NANANA", str2 = "NANA"
    Output: "NA"

Constraints
    1 <= str1.length, str2.length <= 1000
    str1 and str2 consist of English uppercase
    letters

Expected Complexity
    Time  O(m + n)
    Space O(g) for the returned string

    m is len(str1), n is len(str2), and g is the
    gcd of the two lengths.
"""


def solution(str1, str2):
    pass


print("Greatest Common Divisor of Strings", end=" ")
assert solution("ABAB", "AB") == "AB", "example 1 failed"
assert solution("NANANA", "NANA") == "NA", "example 2 failed"
assert solution("LEET", "CODE") == "", "no divisor failed"
assert solution("ABCABC", "ABCABC") == "ABCABC", "equal strings failed"
print("OK")