## Algorithm

Problem Name: 1071. Greatest Common Divisor of Strings

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

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: ""
```

Constraints:

• `1 <= str1.length, str2.length <= 1000`
• `str1` and `str2` consist of English uppercase letters.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String gcdOfStrings(String str1, String str2) {
if (str1.length() < str2.length()) {
return gcdOfStrings(str2, str1);
} else if (!str1.startsWith(str2)) {
return "";
} else if (str2.isEmpty()) {
return str1;
} else {
return gcdOfStrings(str1.substring(str2.length()), str2);
}
}
}
``````
Copy The Code &

Input

cmd
str1 = "ABCABC", str2 = "ABC"

Output

cmd
"ABC"

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const gcdOfStrings = function(str1, str2) {
let res = "";

if (str1[0] !== str2[0]) return res;
if (str1[str1.length - 1] !== str2[str2.length - 1]) return res;
let s = str1[0];
let e = str1[str1.length - 1];

let loopStr = str1.length > str2.length ? str2 : str1;
for (let i = 1, len = loopStr.length; i  <  len; i++) {
if (loopStr[i] !== e) continue;
let tmp = loopStr.slice(0, i + 1);
let ok1 = false;
let ok2 = false;
let t1 = "";
let t2 = "";
while (t1.length  <  str1.length) {
t1 += tmp;
if (t1 === str1) {
ok1 = true;
break;
}
}
while (t2.length  <  str2.length) {
t2 += tmp;
if (t2 === str2) {
ok2 = true;
break;
}
}

if (ok1 && ok2 && tmp.length > res.length) res = tmp;
}

return res;
};
``````
Copy The Code &

Input

cmd
str1 = "ABCABC", str2 = "ABC"

Output

cmd
"ABC"

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if len(str1) == len(str2):
return str1 if str1==str2 else ''
else:
if len(str1) < len(str2):
str1,str2 = str2,str1
if str1[:len(str2)] == str2:
return self.gcdOfStrings(str1[len(str2):],str2)
else:
return ''
``````
Copy The Code &

Input

cmd
str1 = "ABABAB", str2 = "ABAB"

Output

cmd
"AB"

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Text;

namespace LeetCode
{
public class _1071_GreatestCommonDivisorOfStrings
{
public string GcdOfStrings(string str1, string str2)
{
if (str1 == str2) return str1;
if (str1.Length > str2.Length) return GcdOfStrings(str2, str1);

var i = 1;
while (i  < = str1.Length)
{
var length = str1.Length / i;
if ((str1.Length % length == 0) && (str2.Length % length == 0))
{
var sb1 = new StringBuilder();
var sb2 = new StringBuilder();

var result = str1.Substring(0, length);

var x1 = str1.Length / length;
for (int j = 0; j  <  x1; j++)
sb1.Append(result);
var x2 = str2.Length / length;
for (int j = 0; j  <  x2; j++)
sb2.Append(result);

if ((str1 == sb1.ToString()) && (str2 == sb2.ToString()))
return result;
}
i++;
}

return string.Empty;
}
}
}
``````
Copy The Code &

Input

cmd
str1 = "ABABAB", str2 = "ABAB"

Output

cmd
"AB"