## Description
>For two strings s and t, we say "t divides s" if and only if s = 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`.

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

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

## Example2
Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
## Example3
Input: str1 = "LEET", str2 = "CODE"
Output: ""

## Solution
看到題目的意思大概可以往GCD(最大公因數)去猜，看到題目測資時跟我想得很接近，一開始還自己去查了GCD Function怎麼寫，後來發現有現成的可以用。
一開始先判斷兩個字串組成有沒有相同的字母，如果沒有那就去找兩個字串長度的GCD，會發現很剛好的是會回傳答案所需要的東西。

* Time complexity: O(n)
* Space complexity: O(n)

## Code
### C++

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if(str1 + str2 != str2 + str1)
            return "";
        return str1.substr(0,__gcd(str1.size(),str2.size()));
    }
};

### Python3

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