Repeated Substring Pattern
Repeated Substring Pattern: decide whether a string can be built by repeating some substring block two or more times.
- 1 <= s.length <= 10⁴
- s consists of lowercase English letters.
Intuition
Repeated substring pattern asks whether a string can be built by repeating one of its substrings two or more times.
A direct approach tries every candidate length. A valid pattern's length must divide the string's length evenly, so only divisors need testing — and only up to n/2, since the pattern must repeat at least twice. For each divisor, check whether repeating that prefix reproduces the string.
That is O(n√n) at worst and perfectly acceptable.
The elegant solution is a single line, and worth understanding rather than memorising:
- Concatenate the string with itself, strip the first and last characters, and check whether the original still appears inside.
The reasoning: if s is p repeated k times, then s + s is p repeated 2k times. Removing one character from each end destroys the two original copies but leaves p repeated enough times that s still occurs somewhere in the middle.
If s has no repeating pattern, the only occurrences of s within s + s are the two original ones, and stripping the ends removes both.
The stripping is essential. Without it, s always appears in s + s and every string returns true.
The KMP approach uses the failure function: n − lps[n-1] gives the shortest candidate period, and the string is periodic when that value divides n evenly and is not n itself. This is O(n) and is what the problem is really pointing at.
A single-character string returns false, since a pattern must repeat at least twice.
A repeating block's length must divide the string's length evenly, so only divisors up to n/2 need testing. Checking block * (n // length) == s verifies the whole construction in one comparison.
Approach
Before reading on: price up what the direct approach costs here, then ask what you are recomputing on every character that could be carried instead. Aim for O(n^2) worst case time and O(n) space.
Test only divisor lengths
A valid pattern's length must divide n evenly, and be at most n/2 since it repeats twice or more. Only those candidates need checking.
Know the concatenation trick
Check whether s appears in (s + s) with the first and last characters removed. One line, and it answers the question completely.
Understand why it works
If s is p repeated k times, s + s is p repeated 2k times — stripping the ends destroys the two original copies but leaves s visible in the middle.
Never skip the stripping
Without removing the end characters, s always appears in s + s and every input returns true. The strip is what makes the test meaningful.
Or use the KMP failure function
n - lps[n-1] is the shortest candidate period. The string is periodic when that value divides n and is not n itself — O(n) and the intended solution.
Reject single characters
A one-character string cannot repeat twice, so the answer is false. The divisor loop handles this by never running.
Cost of the approaches
The divisor scan is O(n√n), the concatenation check O(n) with O(n) space, and KMP O(n) time and space.
Solution & live demo
Common pitfalls
Testing lengths that don't divide n
for length in range(1, n // 2 + 1):
block = s[:length]
...if n % length != 0:
continueA block that doesn't tile the string exactly can never reconstruct it, so the work is wasted — and a naive comparison against a truncated repetition can produce a false positive on a partial final block.
Looping past n // 2
for length in range(1, n + 1):
for length in range(1, n // 2 + 1):
The pattern must repeat at least twice, so its length is at most half the string. Including n itself makes every string trivially match itself once and returns true for all input.
Comparing only the first two blocks
if s[:length] == s[length:2*length]: return True
if block * (n // length) == s:
Two matching blocks say nothing about the rest — "ababcd" passes that test and fails the real one. The full reconstruction has to be compared against the entire string.
Edge cases
no candidate length <= len(s)//2 exists, loop doesn't run, returns False
only L=1 could divide it before len(s)//2, but a single repeated character rarely matches unless all chars are equal
L=1 divides and rebuilding matches immediately
smallest matching L is found first since the loop goes in increasing order