38 · Segment Trees, Fenwick & String Matching
#459 Repeated Substring Pattern
the problem
In plain words
Return true if s can be built by repeating one of its substrings two or more times.
in s = "abab"
out true
"ab" twice.
in s = "aba"
out false
in s = "abcabcabcabc"
out true
"abc" four times (or "abcabc" twice).
- 1 ≤ s.length ≤ 10⁴
- Lowercase English letters
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternKMP / prefix function
If s has a border of length b (a prefix that is also a suffix), then s has period n − b. s is a repetition exactly when its smallest period divides n and is smaller than n.
solutions
From brute force to optimal
For each length L that divides n (up to n/2), repeat s[0..L) and compare.
- For L in 1..n/2 with n % L == 0.
- Check unit.repeat(n / L).equals(s).
Each check is O(n); d(n) = number of divisors of n (at most 64 for n ≤ 10⁴).
The repeated string built for comparison.
class Solution { public boolean repeatedSubstringPattern(String s) { int n = s.length(); for (int len = 1; len <= n / 2; len++) { if (n % len != 0) continue; // the unit must tile s exactly String unit = s.substring(0, len); if (unit.repeat(n / len).equals(s)) return true; } return false; }}s is periodic iff s occurs inside s + s at a position other than 0 and n.
- Search s in s + s starting from index 1.
- True if the first hit is before index n.
The JDK search is naive in the worst case; with KMP it would be O(n).
The doubled string.
class Solution { public boolean repeatedSubstringPattern(String s) { // s is periodic <=> s appears in s+s somewhere other than position 0 and position n return (s + s).indexOf(s, 1) < s.length(); }}Compute lps; border = lps[n−1], period = n − border. Answer: border > 0 and n % period == 0.
- Build lps in O(n).
- border = lps[n − 1].
- Return border > 0 && n % (n − border) == 0.
One prefix-function pass.
The lps array.
class Solution { public boolean repeatedSubstringPattern(String s) { int n = s.length(); int[] lps = new int[n]; for (int i = 1, len = 0; i < n; i++) { while (len > 0 && s.charAt(i) != s.charAt(len)) len = lps[len - 1]; if (s.charAt(i) == s.charAt(len)) len++; lps[i] = len; } int border = lps[n - 1]; // longest proper prefix that is also a suffix int period = n - border; // smallest shift that maps s onto itself return border > 0 && n % period == 0; }}in the room
How to say it in the interview
talk track
- Give the doubled-string trick as a one-liner, then prove it or offer the prefix-function version for a guaranteed O(n).
traps
- Accepting the whole string as its own unit — the repetition must happen at least twice (border > 0).
what they ask next
Follow-ups
Find the smallest repeating unit?
It's s.substring(0, n − lps[n−1]) when the check passes; otherwise s itself.
before you submit
Edge cases to test
- One character → false (it needs at least two copies)
- "aa" → true
- A border that is not a period: "aabaaba" → false
- Prime length with mixed letters → false
practise next
Similar problems
- #1392Longest Happy PrefixHardin Range Queries & Strings
- #28Find the Index of the First Occurrence in a StringEasyin Range Queries & Strings
- #214Shortest PalindromeHardin Range Queries & Strings