# leetcode\_1071

For strings S and T, we say "T divides S" if and only if S = T + ... + T (T concatenated with itself 1 or more times)

Return the largest string X such that X divides str1 and X divides 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: ""

Note:

1 <= str1.length <= 1000 1 <= str2.length <= 1000 str1\[i] and str2\[i] are English uppercase letters.

## Solutions

1. **math**
2. from the official answer
3. `s1 + s2 == s2 + s1` is the sufficient requirement for the existence of `x` such that `s1 = nx, s2 = mx`

```cpp
class Solution {
public:
    int gcd(int a, int b) {
        while (b) {
            a %= b;
            swap(a, b);
        }
        return a;
    }
    string gcdOfStrings(string str1, string str2) {
        if (str1 + str2 != str2 + str1) return "";
        return str1.substr(0, gcd(str1.size(), str2.size()));
    }
};
```