'''
For two strings s and t, we say "t divides s" if and only if s = t + ... + t  (t concatenated with itself 1 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: ""
Example 4:

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


Constraints:

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


class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        repeat = ''
        for n in range(len(str1)):
            if len(str1) % (n+1) == 0 and all(str1[0: n+1] == str1[m: m+n+1] for m in range(0, len(str1), n+1)):
                if len(str2) % (n+1) == 0 and all(str1[0: n+1] == str2[m: m+n+1] for m in range(0, len(str2), n+1)):
                    repeat = str1[0: n+1]
        return repeat