Repeated Substring Pattern — Solution in Python, Java & C++
Repeated Substring Pattern solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Repeated Substring Pattern is an easy coding problem on strings and string matching, asked in Amazon, Google, Microsoft and Myntra interviews.
- Difficulty: Easy
- Topics: Strings, String Matching
- Asked at: Amazon, Google, Microsoft, Myntra
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s, return true if it can be built by taking one of its proper substrings and concatenating multiple copies of it.
Example 1
Input: s = "abab"
Output: true
Explanation: It is "ab" twice.
Example 2
Input: s = "aba"
Output: false
Example 3
Input: s = "abcabcabcabc"
Output: true
Explanation: It is "abc" four times.
Constraints
1 <= s.length <= 40s consists of lowercase English letters.
Hints for Repeated Substring Pattern
Hint 1
The repeating unit's length must divide the string's length, and be at most half of it.
Hint 2
Test each such length by comparing every block against the first one.
Hint 3
A neat trick:
shas this property exactly when it appears inside(s + s)with the first and last characters removed.
How to solve Repeated Substring Pattern
The repeating unit's length must divide n and be at most n/2; for each such length, check whether repeating the prefix reproduces the string.
Approach
- For each
lengthfrom 1 ton // 2, skip it unless it dividesn. - Build
s[:length]repeatedn / lengthtimes and compare withs. - Return
trueon the first match,falseif none.
Why it works
If s is u repeated k >= 2 times then |u| divides n, |u| <= n/2, and u is precisely the prefix of that length — so the check is both necessary and sufficient.
Complexity
- Time —
O(n · d(n)) whered(n)is the number of divisors - Space —
O(n)
Pitfalls
- The one-liner
s in (s + s)[1:-1]is equivalent and O(n) with a linear-time search. - Testing non-divisor lengths wastes time and can never match.
Reference solution
Python
def repeatedSubstringPattern(s: str) -> bool:
n = len(s)
for length in range(1, n // 2 + 1):
if n % length != 0:
continue
if s[:length] * (n // length) == s:
return True
return FalseJava
public static boolean repeatedSubstringPattern(String s) {
int n = s.length();
for (int len = 1; len <= n / 2; len++) {
if (n % len != 0) continue;
String unit = s.substring(0, len);
boolean ok = true;
for (int i = len; i < n; i += len) {
if (!s.substring(i, i + len).equals(unit)) {
ok = false;
break;
}
}
if (ok) return true;
}
return false;
}C++
bool repeatedSubstringPattern(string s) {
int n = (int) s.size();
for (int len = 1; len <= n / 2; len++) {
if (n % len != 0) continue;
bool ok = true;
for (int i = len; i < n; i++) {
if (s[i] != s[i - len]) { ok = false; break; }
}
if (ok) return true;
}
return false;
}JavaScript
var repeatedSubstringPattern = function(s) {
const n = s.length;
for (let len = 1; len <= Math.floor(n / 2); len++) {
if (n % len !== 0) continue;
const unit = s.slice(0, len);
let ok = true;
for (let i = len; i < n; i += len) {
if (s.slice(i, i + len) !== unit) { ok = false; break; }
}
if (ok) return true;
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings