Repeated Substring Pattern

Easy

#0446Time: 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.1 company

Patterns

String Matching

Data structures

String

Companies

Myntra

Prompt

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

4 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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.

1class Solution {2    public boolean repeatedSubstringPattern(String s) {3        int n = s.length();4        for (int l = 1; l <= n / 2; l++) {5            if (n % l == 0) {6                String sub = s.substring(0, l);7                boolean match = true;8                for (int j = l; j < n; j += l) {9                    if (!s.substring(j, j + l).equals(sub)) {10                        match = false;11                        break;12                    }13                }14                if (match) {15                    return true;16                }17            }18        }19        return false;20    }21}

Complexity

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.

Trade-offs

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.

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.

Algorithm

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

Walkthrough

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.

1class Solution {2    public boolean repeatedSubstringPattern(String s) {3        int n = s.length();4        for (int l = n / 2; l >= 1; l--) {5            if (n % l == 0) {6                int k = n / l;7                String sub = s.substring(0, l);8                StringBuilder sb = new StringBuilder();9                for (int i = 0; i < k; i++) {10                    sb.append(sub);11                }12                if (sb.toString().equals(s)) {13                    return true;14                }15            }16        }17        return false;18    }19}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Compute the KMP LPS array for the input string s of length n.
Get the length of the longest proper prefix that is also a suffix: len = lps[n-1].
Calculate the length of the potential repeating unit: subLen = n - len.
If len > 0 and n % subLen == 0, return true.
Otherwise, return false.

Walkthrough

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.

1class Solution {2    public boolean repeatedSubstringPattern(String s) {3        int n = s.length();4        if (n < 2) return false;5        6        int[] lps = new int[n];7        int length = 0; // Length of the previous longest prefix suffix8        int i = 1;9        lps[0] = 0;10 11        while (i < n) {12            if (s.charAt(i) == s.charAt(length)) {13                length++;14                lps[i] = length;15                i++;16            } else {17                if (length != 0) {18                    length = lps[length - 1];19                } else {20                    lps[i] = 0;21                    i++;22                }23            }24        }25 26        int len = lps[n - 1];27        return len > 0 && n % (n - len) == 0;28    }29}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Given the string s of length n.
Create a new string t = s + s.
Check if the substring of t from index 1 to 2*n - 2 (i.e., t without its first and last characters) contains s.
Return the result of this check.

Walkthrough

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.

1class Solution {2    public boolean repeatedSubstringPattern(String s) {3        String t = s + s;4        return t.substring(1, t.length() - 1).contains(s);5    }6}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  boolean repeatedSubstringPattern(String s) {4    String str = s + s;5    return str.substring(1, str.length() - 1).contains(s);6  }7}

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

1class Solution {2public:3  bool repeatedSubstringPattern(string s) {4    return (s + s).find(s, 1) < s.size();5  }6};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  boolean repeatedSubstringPattern(String s) {4    String str = s + s;5    return str.substring(1, str.length() - 1).contains(s);6  }7}

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

1class Solution {2public:3  bool repeatedSubstringPattern(string s) {4    return (s + s).find(s, 1) < s.size();5  }6};

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.