#459
Repeated Substring Pattern
Easy Doubling trick / LPS
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether s can be built by repeating one of its substrings two or more times.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: is the string some block repeated 2+ times?
Why this works: if it is, the leftover after removing the longest border (lps[n-1]) is the block length, and it divides n.
Example: "abcabc"
lps last = 3 → block length 6 - 3 = 36 % 3 = 0 → true ("abc")
✦Hints open one at a time
If s is a repetition, then s appears inside (s + s) with its first and last character removed.
With KMP: let L = lps[n − 1]. s repeats exactly when L > 0 and n is divisible by n − L.
↗Approach
Compute the LPS array. The smallest repeating block has length n − lps[n − 1]; check that it's shorter than n and divides n.
</>Solution (Java)
class Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
int[] lps = new int[n];
for (int i = 1, len = 0; i < n; ) {
if (s.charAt(i) == s.charAt(len)) lps[i++] = ++len;
else if (len > 0) len = lps[len - 1];
else lps[i++] = 0;
}
int border = lps[n - 1];
return border > 0 && n % (n - border) == 0; // block length = n - border
}
}!Common mistake
Using (s + s).contains(s) without trimming the ends — it's always true.
Complexity
- Time: O(n).
- Space: O(n).
Topic: String Pattern Matching
🎬 Episodes 18–19: video coming soon