1071. Greatest Common Divisor of Strings

#string

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

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

Space Complexity	Time Complexity
$\text{O}()$	$\text{O}()$

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;
}