# Repeated Substring Pattern
**Difficulty:** EASY
[External](https://leetcode.com/problems/repeated-substring-pattern)
Canonical: https://scaleengineer.com/dsa/problems/repeated-substring-pattern
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** String
**Companies:** [Myntra](https://scaleengineer.com/companies/myntra)
---
## Problem
Given a string `s`, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

**Example 1:**

**Input:** s = "abab"
**Output:** true
**Explanation:** It is the substring "ab" twice.

**Example 2:**

**Input:** s = "aba"
**Output:** false

**Example 3:**

**Input:** s = "abcabcabcabc"
**Output:** true
**Explanation:** It is the substring "abc" four times or the substring "abcabc" twice.

**Constraints:**

* `1 <= s.length <= 104`
* `s` consists of lowercase English letters.

# Approaches
## Brute Force Iteration
This approach tests every possible length for the repeating substring. A valid substring must have a length `l` that is a divisor of the total string length `n`. We can iterate through all possible lengths `l` from 1 up to `n/2`. For each `l`, we check if the entire string `s` is formed by repeating the prefix of length `l`.
**Time:** O(n^2) - The outer loop runs `n/2` times. For each length `l`, the inner loop performs `n/l - 1` substring comparisons. Each comparison of length `l` takes `O(l)` time. The total work for a given `l` is `(n/l) * O(l) = O(n)`. Since the outer loop runs `O(n)` times, the total complexity is `O(n^2)`. · **Space:** O(n) - In each iteration, we create a substring `sub` of length `l`. The maximum length of `l` is `n/2`. In Java, `substring` creates a new string, so the space complexity is dominated by the storage for these substrings.
**Pros:** Simple to understand and implement.; A straightforward, direct translation of the problem statement.
**Cons:** Inefficient for long strings, as it checks many unnecessary lengths.; Likely to result in a 'Time Limit Exceeded' error on competitive programming platforms for larger inputs.
### Explanation
The algorithm iterates through possible substring lengths `l` from 1 to `s.length() / 2`. For a length `l` to be a candidate, we first check if the total length `n` is divisible by `l`. If it is, we extract the first substring of length `l`, let's call it `sub`. We then verify if the rest of the string `s` consists of repetitions of `sub`. This is done by comparing `sub` with every subsequent block of `l` characters in `s`. If all blocks match `sub`, we have found a valid pattern and return `true`. If we find a mismatch, we move on to the next possible length. If the loop completes without finding any such pattern, we return `false`.

```java
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int l = 1; l <= n / 2; l++) {
            if (n % l == 0) {
                String sub = s.substring(0, l);
                boolean match = true;
                for (int j = l; j < n; j += l) {
                    if (!s.substring(j, j + l).equals(sub)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
1. Get the length of the string, `n`.
2. Iterate `l` from 1 to `n / 2`.
3. If `n` is divisible by `l`:
    a. Extract the substring `sub = s.substring(0, l)`.
    b. Assume the pattern holds (`match = true`).
    c. Iterate `j` from `l` to `n - l` with a step of `l`.
    d. If `s.substring(j, j + l)` is not equal to `sub`, set `match = false` and break the inner loop.
    e. If `match` is still true after the inner loop, return `true`.
4. If the outer loop finishes, return `false`.

## Optimized Iteration using Divisors
The brute-force approach can be optimized by realizing that the length of the repeating substring `l` must be a divisor of the total string length `n`. Instead of checking every length from 1 to `n/2`, we only need to check the lengths that are actual divisors of `n`.
**Time:** O(d(n) * n) - where `d(n)` is the number of divisors of `n`. For each divisor `l`, we perform a check that takes `O(n)` time (to build and compare the string). The number of divisors `d(n)` is much smaller than `n`, making this a significant improvement over `O(n^2)`. · **Space:** O(n) - In the worst case, we construct a new string of length `n` for comparison.
**Pros:** Much more efficient than the naive brute-force approach.; Passes most test cases on typical online judges.; The logic is still relatively easy to follow.
**Cons:** The time complexity is dependent on the number of divisors of `n`, which can still be slow for certain numbers.; Still involves string construction and comparison which can be less efficient than character-level manipulation.
### Explanation
This method improves upon brute force by reducing the number of candidate lengths to check. We iterate through possible lengths `l` from `n/2` down to 1. For each `l`, we first check if it's a divisor of `n`. If it is, we extract the prefix of length `l` as the potential repeating substring, `sub`. Then, we construct a test string by appending `sub` to itself `n/l` times. If this newly constructed string is identical to the original string `s`, we have found our pattern and can return `true`. If we check all divisors and none form a valid pattern, we return `false`. This significantly reduces the number of checks compared to the naive brute-force, especially when `n` has few divisors.

```java
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int l = n / 2; l >= 1; l--) {
            if (n % l == 0) {
                int k = n / l;
                String sub = s.substring(0, l);
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < k; i++) {
                    sb.append(sub);
                }
                if (sb.toString().equals(s)) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
1. Get the length of the string, `n`.
2. Iterate `l` from `n / 2` down to 1.
3. If `n` is divisible by `l`:
    a. Calculate the number of repetitions `k = n / l`.
    b. Extract the substring `sub = s.substring(0, l)`.
    c. Construct a new string by appending `sub` `k` times.
    d. If the constructed string is equal to `s`, return `true`.
4. If the loop finishes, return `false`.

## KMP Algorithm
This problem can be rephrased as finding if the string `s` is periodic. The Knuth-Morris-Pratt (KMP) algorithm's preprocessing step, which computes a Longest Proper Prefix Suffix (LPS) array, can be used to solve this efficiently in linear time.
**Time:** O(n) - The computation of the LPS array takes linear time. The final check is an O(1) operation. · **Space:** O(n) - We need an array of size `n` to store the LPS values.
**Pros:** Optimal time complexity.; Provides a fundamental understanding of the string's periodic properties.; Efficient in practice as it works with arrays and avoids heavy string object manipulation.
**Cons:** The logic of the KMP algorithm and the LPS array can be complex to understand and implement correctly from scratch.
### Explanation
The LPS array `lps` for a string `s` of length `n` stores at each index `i` the length of the longest proper prefix of `s[0...i]` that is also a suffix of `s[0...i]`. We first compute this LPS array for `s`. The value `lps[n-1]`, let's call it `len`, gives the length of the longest proper prefix of `s` that is also a suffix. If `s` is formed by repeating a substring `sub` of length `subLen`, then `len` will be `n - subLen`. This means the candidate repeating substring has a length of `n - len`. For this to be a valid pattern, two conditions must be met: `len` must be greater than 0 (to ensure a non-empty pattern), and the total length `n` must be divisible by the pattern's length `n - len`. If both hold, the string has a repeated substring pattern.

```java
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        if (n < 2) return false;
        
        int[] lps = new int[n];
        int length = 0; // Length of the previous longest prefix suffix
        int i = 1;
        lps[0] = 0;

        while (i < n) {
            if (s.charAt(i) == s.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        int len = lps[n - 1];
        return len > 0 && n % (n - len) == 0;
    }
}
```
### Algorithm
1. Compute the KMP LPS array for the input string `s` of length `n`.
2. Get the length of the longest proper prefix that is also a suffix: `len = lps[n-1]`.
3. Calculate the length of the potential repeating unit: `subLen = n - len`.
4. If `len > 0` and `n % subLen == 0`, return `true`.
5. Otherwise, return `false`.

## String Concatenation Trick
A surprisingly concise and clever solution exists for this problem. If a string `s` is composed of a repeating substring, then concatenating `s` with itself (`s+s`) will contain the original string `s` as a substring, even after removing the first and last characters of the concatenated string.
**Time:** O(n) - String concatenation `s+s` takes `O(n)`. The `substring` operation also takes `O(n)`. The `contains` method, using an efficient string searching algorithm like KMP or Boyer-Moore, takes `O(n)`. Thus, the total time complexity is linear. · **Space:** O(n) - We create a new string `t` of length `2n` and another temporary substring, resulting in linear space usage.
**Pros:** Extremely concise, elegant, and easy to remember.; Optimal time complexity.; Leverages powerful built-in string manipulation functions.
**Cons:** The logic behind why it works is not immediately obvious and feels like a 'magic' trick.; May have slightly more overhead in practice than a manual KMP implementation due to string object creation and internal workings of library functions.
### Explanation
Let the string `s` be formed by repeating a substring `sub`. For example, if `s = "abab"`, then `sub = "ab"`. The concatenated string `t = s + s` would be `"abababab"`. This new string `t` contains multiple copies of `s`. Specifically, `s` appears starting at index 0, but also at index `l` (the length of `sub`). Since `l` must be less than `n`, this second occurrence starts before index `n`. If we remove the first and last characters of `t` (to get `"bababa"`), the original string `s` (`"abab"`) is still present. This property holds if and only if `s` is a repeated substring pattern. Therefore, the entire problem reduces to a single line of code that performs this check.

```java
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String t = s + s;
        return t.substring(1, t.length() - 1).contains(s);
    }
}
```
### Algorithm
1. Given the string `s` of length `n`.
2. Create a new string `t = s + s`.
3. Check if the substring of `t` from index 1 to `2*n - 2` (i.e., `t` without its first and last characters) contains `s`.
4. Return the result of this check.

# Solutions
### Java

```java
class Solution {
public
  boolean repeatedSubstringPattern(String s) {
    String str = s + s;
    return str.substring(1, str.length() - 1).contains(s);
  }
}

```

### Python

```python
class Solution:
    def repeatedSubstringPattern(
        self, s: str) -> bool: return (s + s). index(s, 1) < len(s)

```

### CPP

```cpp
class Solution {
public:
  bool repeatedSubstringPattern(string s) {
    return (s + s).find(s, 1) < s.size();
  }
};

```