---
description: '#string'
---

# 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`.

{% hint style="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)
{% endhint %}



***

### 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.

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