# LeetCode 1071: Greatest Common Divisor of Strings

## Problem Restatement

We say string `t` divides string `s` if `s` is formed by concatenating `t` one or more times.

We are given two strings `str1` and `str2`.

Return the largest string `t` that divides both `str1` and `str2`.

The official constraints state that `1 <= str1.length, str2.length <= 1000`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Strings `str1` and `str2` |
| Output | Largest common divisor string |

Function shape:

```python
def gcdOfStrings(str1: str, str2: str) -> str:
    ...
```

## Examples

Example 1:

```python
str1 = "ABCABC", str2 = "ABC"
```

`"ABC"` divides both: `"ABCABC" = "ABC" * 2`, `"ABC" = "ABC" * 1`.

Answer:

```python
"ABC"
```

Example 2:

```python
str1 = "ABABAB", str2 = "ABAB"
```

`"AB"` divides both.

Answer:

```python
"AB"
```

## Key Insight

If a string `t` divides both `str1` and `str2`, then `t` also divides `str1 + str2` and `str2 + str1`. So `str1 + str2 == str2 + str1` is a necessary condition.

If this condition holds, the GCD divisor string has length `gcd(len(str1), len(str2))`.

## Correctness

If `str1 + str2 != str2 + str1`, no common divisor exists (return `""`).

Otherwise, the largest divisor must have a length that divides both `len(str1)` and `len(str2)`, so its length is `gcd(len(str1), len(str2))`.

## Edge Cases

- Check the minimum input size allowed by the constraints.
- Verify duplicate values or tie cases if the input can contain them.
- Keep the return value aligned with the exact failure case in the statement.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m + n)` | String concatenation and GCD |
| Space | `O(m + n)` | Concatenated strings |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
from math import gcd

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if str1 + str2 != str2 + str1:
            return ""
        return str1[:gcd(len(str1), len(str2))]
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.gcdOfStrings("ABCABC", "ABC") == "ABC"
    assert s.gcdOfStrings("ABABAB", "ABAB") == "AB"
    assert s.gcdOfStrings("LEET", "CODE") == ""
    assert s.gcdOfStrings("AA", "A") == "A"

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---|---|
| `"ABCABC","ABC"` | `"ABC"` | GCD length = 3 |
| `"ABABAB","ABAB"` | `"AB"` | GCD length = 2 |
| `"LEET","CODE"` | `""` | No common divisor |
| `"AA","A"` | `"A"` | GCD length = 1 |