Comment on page

# 1071.Greatest Common Divisor of Strings

1071.Greatest Common Divisor of Strings

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.

class Solution {
public:
string gcdOfStrings(string str1, string str2) {
if(str1.length()==str2.length()) return str1==str2?str1:"";
// cout<<str1.length() <<" "<< str2.length()<<endl;
if(str1.length()< str2.length()) swap(str1, str2);
int n=str1.length()/str2.length();
int m=str1.length()%str2.length();
// cout<<n<<" "<< m<< endl;
for(int i=1;i<n;i++)
{
for(int j=0;j<str2.length();j++)
{
if(str2[j]!=str1[j+i*str2.length()]) return "";
}
}
if(m==0) return str2;
return gcdOfStrings(str2,str2.substr(0,m));
}
};