Repeated Substring Pattern

EASY

Description

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 <= 10⁴
s consists of lowercase English letters.

Approaches

Checkout 4 different approaches to solve Repeated Substring Pattern. Click on different approaches to view the approach and algorithm in detail.

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.

Algorithm

Get the length of the string, n.
Iterate l from 1 to n / 2.
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.
If the outer loop finishes, return false.

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.

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

Complexity Analysis

Time Complexity: 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 Complexity: 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 and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Repeated Substring Pattern. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Repeated Substring Pattern

Patterns:

String Matching

Data Structures:

String

Companies:

Myntra |