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.

&nbsp;
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: ""


&nbsp;
Constraints:


	1 &lt;= str1.length, str2.length &lt;= 1000
	str1 and str2 consist of English uppercase letters.


class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:

        if len(str2) > len(str1):
            str1, str2 = str2, str1

        curr_str2 = str2
        while True:

            rep = len(str1)//len(curr_str2)

            if curr_str2*rep == str1:
                return curr_str2

            found = False
            for i in range(len(curr_str2)-1, 1, -1):
                try_str2 = curr_str2[:i]
                rep2 = len(str2)//len(try_str2)

                if try_str2*rep2 == str2:
                    curr_str2 = try_str2
                    found = True
                    break

            if not found:
                break
        return ""
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        
        int length1 = str1.length();
        int length2 = str2.length();
        String temp;
        
        for(int i=gcd(length1,length2); i>0 && length1 % i == 0 && length2 % i == 0; i--) {
            if(str1.substring(0,i).equals(str2.substring(0,i))) {
                if(doesRepeat(str1.substring(0,i),str1,str2))
                    return str1.substring(0,i);
            }
        }
        return "";
        
    }
    public int gcd(int a, int b) {
        if(b==0)
            return a;
        return gcd(b,a % b);
    }
    public boolean doesRepeat(String s, String str1, String str2) {
        int sLength = s.length();
        boolean bool1 = true, bool2 = true;
        String temp = str1,temp2;
        
        while(sLength < temp.length()) {
            temp2 = temp.substring(sLength,sLength*2);
            
            if(s.equals(temp2));
            else
                bool1 = false;
            temp = temp.substring(sLength,temp.length());
        }
        temp = str2;
        while(sLength < temp.length()) {
            temp2 = temp.substring(sLength,sLength*2);
            if(s.equals(temp2));
            else
                bool2 = false;
            temp = temp.substring(sLength,temp.length());
        }
        return bool1 && bool2;
    }
    
}
class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        int m = str1.length(), n = str2.length();
        int temp = __gcd(m, n);
        string str;
        if(str1 + str2 == str2 + str1) str = str1.substr(0, temp);
        return str;
    }
};
/**
 * @param {string} str1
 * @param {string} str2
 * @return {string}
 */
var gcdOfStrings = function(str1, str2) {
  const gcdOfNumber = (num1, num2) => {
    while (num2 !== 0) {
      const res = num2 % num1
      num1 = num2
      num2 = res
    }
    return num1
  }
  const gcd = gcdOfNumber(str1.length, str2.length)
  const common = str1.slice(0, gcd)
  return common.repeat(str1.length / gcd) === str1 &&
    common.repeat(str2.length / gcd) === str2
    ? common
    : ''
}
Greatest Common Divisor of Strings