What it teaches: The lps of the whole string reveals its smallest period.
Practise it on judges as “Repeated Substring Pattern”.
In plain words
Is this string just one small block copied several times, like "abc" repeated into "abcabcabcabc"? A neat trick: glue the string to itself and chop off the first and last letters. If the original string still shows up inside, it must be made of repeats.
Return true if s is a smaller piece repeated two or more times. Example: s = "abcabcabcabc" → true.
The problem
Return true if s can be built by repeating a substring of itself two or more times.
Example 1
Input: s = "abcabcabcabc"
Output: true
Example 2
Input: s = "aba"
Output: false
Constraints
1 ≤ n ≤ 10⁴
Pattern clues in the wording
→ String made of repeated blocks
These clues point to String Matching (KMP, Z, Rolling Hash): Find a pattern inside a text in linear time by reusing what earlier comparisons already proved, or by comparing hashes instead of characters.
Stuck? Take one hint at a time
Solution · starter
class Solution {
public boolean repeatedSubstringPattern(String s) {
return false;
}
}
Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.
Compute lps; let L = lps[n − 1]; answer = L > 0 && n % (n − L) == 0.
Approach 1
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 L = lps[n - 1];
return L > 0 && n % (n - L) == 0;
}
}
Verdict: One table, one check.
2
Doubled string
Time O(n) with KMP; indexOf is usually fine Space O(n)
s is periodic ⇔ s appears in (s + s) with the first and last characters removed.
▶ Dry run: Find s inside (s + s) minus its endss = "abcabcabcabc"
a
0
b
1
c
2
a
3
b
4
c
5
a
6
b
7
c
8
a
9
b
10
c
11
Step 1/3The string has 12 letters. We want to know if it is a block repeated.
Approach 2
class Solution {
public boolean repeatedSubstringPattern(String s) {
String doubled = s + s;
return doubled.substring(1, doubled.length() - 1).contains(s);
}
}
Verdict: A neat one-liner.
Before you submit
Edge cases and common mistakes
Test these inputs
Single character (false)
All same character (true when n ≥ 2)
Mistakes people make
Checking only divisors up to n / 2 by brute force without early exit (fine, but O(n √n)).