# Greatest Common Divisor of Strings
**Difficulty:** EASY
[External](https://leetcode.com/problems/greatest-common-divisor-of-strings)
Canonical: https://scaleengineer.com/dsa/problems/greatest-common-divisor-of-strings
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys), [Nvidia](https://scaleengineer.com/companies/nvidia), [Datadog](https://scaleengineer.com/companies/datadog)
---
## Problem
For two strings `s` and `t`, we say "`t` divides `s`" if and only if `s = t + t + t + ... + 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.

# Approaches
## Brute Force Iteration
This approach involves checking every possible prefix of the shorter string, from longest to shortest, to see if it can be a common divisor for both `str1` and `str2`.
**Time:** O(min(n, m) * (n + m)), where `n` and `m` are the lengths of the two strings. The loop runs `min(n, m)` times. Inside the loop, the `isDivisor` check for `str1` takes O(n) time and space, and for `str2` it takes O(m) time and space. · **Space:** O(n + m) to store the temporary strings built inside the `isDivisor` helper function for comparison.
**Pros:** Simple to understand and implement.; Correctly solves the problem by exhaustively checking all possibilities.
**Cons:** Highly inefficient, especially for long strings, as it involves many string operations (substring, concatenation, comparison) inside a loop.; Creates many temporary strings, leading to high memory usage.
### Explanation
The core idea is to test all potential candidates for the greatest common divisor string `x`. A candidate for `x` must be a prefix of `str1`. We can iterate through all possible lengths `l` for this prefix, starting from the length of the shorter string down to 1. For each length `l`, we extract the prefix `p = str1.substring(0, l)`. We then define a helper function, `isDivisor(s, p)`, which checks if string `s` is formed by concatenating `p` one or more times. This check involves two steps: first, the length of `s` must be divisible by the length of `p`, and second, `s` must be equal to `p` repeated `s.length() / p.length()` times. In the main loop, for each `prefix`, we call `isDivisor(str1, prefix)` and `isDivisor(str2, prefix)`. The first (and therefore longest) `prefix` for which both checks return true is the answer. If no such prefix is found after checking all possible lengths, we return an empty string. ```java
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        for (int l = Math.min(len1, len2); l >= 1; l--) {
            String candidate = str1.substring(0, l);
            if (isDivisor(str1, candidate) && isDivisor(str2, candidate)) {
                return candidate;
            }
        }
        return "";
    }

    private boolean isDivisor(String s, String p) {
        int len_s = s.length();
        int len_p = p.length();
        if (len_s % len_p != 0) {
            return false;
        }
        int times = len_s / len_p;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < times; i++) {
            sb.append(p);
        }
        return s.equals(sb.toString());
    }
}
```
### Algorithm
- Get the lengths of `str1` and `str2`, let's call them `len1` and `len2`. - Iterate with a loop variable `l` from `min(len1, len2)` down to `1`. - In each iteration, extract a `candidate` prefix from `str1` of length `l`. - Check if this `candidate` string divides both `str1` and `str2` using a helper function. - The helper function `isDivisor(s, p)` checks if `s.length()` is divisible by `p.length()` and if `s` can be constructed by repeating `p`. - If the `candidate` divides both strings, it is the largest one found so far (due to the descending loop), so return it. - If the loop completes without finding a common divisor, return an empty string `""`.

## Optimized Brute Force by Checking Divisors
This approach improves upon the brute-force method by recognizing a key property: if a string `x` divides `str1`, then the length of `x` must be a divisor of the length of `str1`. Therefore, we only need to check lengths that are common divisors of both string lengths.
**Time:** O(min(n, m) * (n + m)). While the number of checks is reduced to the number of common divisors, the worst-case complexity is bounded by the same factors as the naive approach. However, it is significantly faster on average. · **Space:** O(n + m) for the temporary strings built in the `isDivisor` helper function.
**Pros:** More efficient in practice than the naive brute-force by reducing the number of expensive string checks.; Still relatively easy to understand.
**Cons:** Still relies on string construction and comparison within a loop.; The worst-case time complexity is not an improvement over the naive approach.
### Explanation
We can significantly optimize the previous approach. Instead of checking every possible prefix length `l`, we only need to check lengths that are common divisors of both `str1.length()` and `str2.length()`. The algorithm iterates from `l = min(len1, len2)` down to 1. In each iteration, it first checks if `l` is a divisor of both `len1` and `len2`. Only if `l` is a common divisor do we proceed to check if the prefix of that length is the actual string divisor. This reduces the number of times we perform the expensive `isDivisor` check, leading to a faster solution in practice, although the worst-case time complexity remains the same. ```java
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        for (int l = Math.min(len1, len2); l >= 1; l--) {
            if (len1 % l == 0 && len2 % l == 0) {
                String candidate = str1.substring(0, l);
                if (isDivisor(str1, candidate) && isDivisor(str2, candidate)) {
                    return candidate;
                }
            }
        }
        return "";
    }

    private boolean isDivisor(String s, String p) {
        int len_s = s.length();
        int len_p = p.length();
        int times = len_s / len_p;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < times; i++) {
            sb.append(p);
        }
        return s.equals(sb.toString());
    }
}
```
### Algorithm
- Get the lengths of `str1` and `str2`, `len1` and `len2`. - Iterate with a loop variable `l` from `min(len1, len2)` down to `1`. - Inside the loop, add a condition: `if (len1 % l == 0 && len2 % l == 0)`. - Only if `l` is a common divisor of the lengths, proceed with the check. - Extract the `candidate` prefix from `str1` of length `l`. - Use the same `isDivisor` helper function to check if the `candidate` divides both `str1` and `str2`. - If it does, return the `candidate`. - If the loop finishes, return `""`.

## Using Greatest Common Divisor of Lengths
This is the most efficient approach, which leverages a mathematical property of strings. If a string `x` is a common divisor of `str1` and `str2`, then `str1 + str2` must be equal to `str2 + str1`.
**Time:** O(n + m), where `n` and `m` are the lengths of the strings. This is dominated by the string concatenation and subsequent equality check. The GCD calculation is much faster, `O(log(min(n, m)))`. · **Space:** O(n + m) to store the two concatenated strings for the comparison.
**Pros:** Extremely efficient with linear time complexity.; Elegant and concise solution.
**Cons:** Relies on a non-obvious mathematical property of strings (related to Fine & Wilf's theorem on periodicity), which might be difficult to derive from scratch.
### Explanation
This optimal solution is based on a crucial property: a common string divisor `x` exists for `str1` and `str2` if and only if `str1 + str2` equals `str2 + str1`. If this condition is false, no common divisor can exist. If it's true, it guarantees that both strings are made of repetitions of some base string. The largest such base string (our answer) will have a length equal to the greatest common divisor (GCD) of the lengths of `str1` and `str2`. The algorithm is therefore very simple and efficient. ```java
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // Check if they have a common divisor property
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }

        // If they do, the length of the GCD string is the GCD of their lengths
        int gcdLength = gcd(str1.length(), str2.length());
        return str1.substring(0, gcdLength);
    }

    // Helper method to compute GCD using Euclidean algorithm
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### Algorithm
- First, check the fundamental property: concatenate `str1` and `str2` in both orders (`str1 + str2` and `str2 + str1`). - If `(str1 + str2)` is not equal to `(str2 + str1)`, then no common divisor exists. Return `""`. - If they are equal, a common divisor is guaranteed to exist. - Calculate the greatest common divisor (GCD) of the lengths of `str1` and `str2`. Let this be `gcdLength`. - The result is the prefix of `str1` (or `str2`) of length `gcdLength`. Return `str1.substring(0, gcdLength)`.

# Solutions
### Java

```java
class Solution {
public
  String gcdOfStrings(String str1, String str2) {
    if (!(str1 + str2).equals(str2 + str1)) {
      return "";
    }
    int len = gcd(str1.length(), str2.length());
    return str1.substring(0, len);
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
class Solution {
public:
  string gcdOfStrings(string str1, string str2) {
    if (str1 + str2 != str2 + str1)
      return "";
    int n = __gcd(str1.size(), str2.size());
    return str1.substr(0, n);
  }
};

```

### Python

```python
class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str: def check(a, b): c = "" while len(c) < len(b): c += a return c == b for i in range(min(len(str1), len(str2)), 0, - 1): t = str1[: i] if check(t, str1) and check(t, str2): return t return ''

```