1071. Greatest Common Divisor of Strings

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

!!! info String t divides s if and only if s = t + t + t + ... + t + t (i.e., t is concatenated with itself one or more times)

# Intuition

# Approach

# Complexity

# Code

# Alternative

• Select the smaller string
• Iterate over all the sub-string possible
  • If the sub-string repeated string.lenght()/subString.length() is equal to the target strings its a divisor
• If there is a common divisor the strings are formed by repeating some string so we can add them in any order and still get the same result.

public String gcdOfStrings(String str1, String str2) {
	if( !(str1+str2).equals(str2+str1)) return "";
	String smaller = (str1.length() < str2.length()) ? str1 : str2;
	String gcd ="";
	int str1l = str1.length(), str2l = str2.length();
	for (int i = smaller.length(); i > 0; --i) {
		if ( str1l%i == 0 && str2l%i == 0 ) {
			String temp = smaller.substring(0,i);
			int tl = temp.length();
 
			String ts1 = temp.repeat(str1l/tl);
			String ts2 = temp.repeat(str2l/tl);
 
			if(ts1.equals(str1) && ts2.equals(str2)) {
				return temp;
			}
 
		}
	}
 
	return gcd;
}