Repeated Substring Pattern solution and explanation
Google
TCS
9 more videos on this problem
LeetCode 459. Repeated Substring Pattern (Algorithm Explained)Nick White · 8:12 · 44K views
Repeated Substring Pattern | LeetCode 459 | C++, Java, PythonKnowledge Center · 9:20 · 24K views
Repeated Substring Pattern | Full Intuition | Time Complexity | GOOGLE | AMAZON | Leetcode-459codestorywithMIK · 21:35 · 20K views
459. Repeated Substring Pattern || Java || Leetcode || HindiCoding Sphere · 8:13 · 8K views
repeated substring pattern leetcode | leetcode 459 | two pointer | regexNaresh Gupta · 9:39 · 7K views
Repeated Substring Pattern | Leet code 459 | Theory explained + Python codeSai Anish Malla · 7:02 · 6K views
Repeated substring pattern problem (LeetCode #459) [3 solutions] - Inside codeInside code · 8:01 · 4K views
Repeated Substring Pattern - LeetCode #459 with Python, JavaScript and JavaCodingNinja · 11:42 · 3K views
LeetCode 459 - Repeated Substring Pattern Solved (Java)Alkademy Learning · 10:57 · 1K views
459. Repeated Substring Pattern - LeetCode Daily Challenge - JavaScriptLeetCodeWithMonu · 10:13 · 732 views
The problem
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Example 1:
Input: s = "abab" Output: true Explanation: It is the substring "ab" twice.
Example 2:
Input: s = "aba" Output: false
Example 3:
Input: s = "abcabcabcabc" Output: true Explanation: It is the substring "abc" four times or the substring "abcabc" twice.
Constraints:
1 <= s.length <= 104sconsists of lowercase English letters.
Approach overview
Problem Overview: You get a string s. The task is to check whether it can be formed by repeating one of its substrings multiple times. For example, "abab" is valid because repeating "ab" forms the entire string, while "aba" cannot be built from a repeating substring.
Approach 1: Repeated Substring using Substring Check (O(n²) time, O(1) space)
This method tries every possible substring length that could repeat to build the full string. Iterate through possible lengths from 1 to n/2. If the total length n is divisible by the candidate length k, extract the substring s[0:k] and repeat it n/k times. Compare the constructed string with the original. If they match, the string follows a repeating pattern. This approach is straightforward and easy to reason about, but repeated string construction and comparisons lead to O(n²) time in the worst case.
This approach mainly uses basic string operations like slicing, concatenation, and equality checks. It works well for short inputs and is often the first solution people implement during interviews because it clearly demonstrates understanding of the pattern constraint.
Approach 2: Repeated Substring using Doubled String Trick (O(n) time, O(n) space)
This trick relies on a key observation about repeating patterns. If a string s is composed of repeated substrings, then it will appear as an internal substring inside (s + s) after removing the first and last characters. Build a new string t = s + s, then check whether s exists in t[1:-1]. If it does, a repeating pattern must exist.
The intuition comes from string rotation behavior. Concatenating the string with itself creates all possible rotations. A repeating structure guarantees the original string will appear somewhere inside the shifted version. This approach uses efficient substring search provided by most languages' standard libraries, giving an overall complexity of O(n) time and O(n) space.
This technique is common in string matching problems and appears frequently in competitive programming because it transforms the pattern detection problem into a simple containment check.
Recommended for interviews: Start by explaining the substring-length enumeration approach to show you understand how repetition works. Then move to the doubled string trick as the optimized solution. Interviewers usually expect the (s + s) insight because it demonstrates deeper understanding of string structure and pattern behavior while reducing the complexity to linear time.
Approach 1: Repeated Substring using Substring Check
One approach is to take a substring of the given string and repeatedly concatenate to check if it forms the original string. This involves iterating through possible substring lengths and using modular arithmetic to assess potential repeats.
def repeatedSubstringPattern(s):
n = len(s)
for i in range(1, n // 2 + 1):
if n % i == 0:
if s[:i] * (n // i) == s:
return True
return Falseclass Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
for (int i = 1; i <= n / 2; i++) {
if (n % i == 0) {
StringBuilder sb = new StringBuilder();
String part = s.substring(0, i);
for (int j = 0; j < n / i; j++) {
sb.append(part);
}
if (sb.toString().equals(s)) {
return true;
}
}
}
return false;
}
}#include<string>
using namespace std;
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
for (int i = 1; i <= n / 2; ++i) {
if (n % i == 0) {
string t = s.substr(0, i);
bool match = true;
for (int j = i; j < n; j += i) {
if (s.substr(j, i) != t) {
match = false;
break;
}
}
if (match) return true;
}
}
return false;
}
};var repeatedSubstringPattern = function(s) {
let n = s.length;
for (let i = 1; i <= n / 2; i++) {
if (n % i === 0) {
let part = s.substring(0, i);
let repeated = part.repeat(n / i);
if (repeated === s) {
return true;
}
}
}
return false;
};#include <stdbool.h>
#include <string.h>
bool repeatedSubstringPattern(char* s) {
int n = strlen(s);
for (int i = 1; i <= n / 2; ++i) {
if (n % i == 0) {
bool match = true;
for (int j = 0; j < n; ++j) {
if (s[j] != s[j % i]) {
match = false;
break;
}
}
if (match) {
return true;
}
}
}
return false;
}public class Solution {
public bool RepeatedSubstringPattern(string s) {
int n = s.Length;
for (int i = 1; i <= n / 2; i++) {
if (n % i == 0) {
string part = s.Substring(0, i);
bool match = true;
for (int j = i; j < n; j++) {
if (s[j] != part[j % i]) {
match = false;
break;
}
}
if (match) return true;
}
}
return false;
}
}The code checks for substrings of increasing lengths up to half the size of the given string. If the length is divisible by the current substring length, it attempts to reconstruct the string by repeating the substring.
Time Complexity: O(n^2). Space Complexity: O(n).
Approach 2: Repeated Substring using Doubled String Trick
Another approach is using the property of doubled strings. By creating a new string by repeating the original and removing the first and last character, we can check if the original string exists within this new string.
def repeatedSubstringPattern(s):
return (s + s)[1:-1].find(s) != -1class Solution {
public boolean repeatedSubstringPattern(String s) {
String ss = s + s;
return ss.substring(1, ss.length() - 1).contains(s);
}
}#include<string>
using namespace std;
class Solution {
public:
bool repeatedSubstringPattern(string s) {
string ss = s + s;
return ss.substr(1, ss.size() - 2).find(s) != string::npos;
}
};var repeatedSubstringPattern = function(s) {
let doubled = s + s;
return doubled.slice(1, -1).includes(s);
};#include <stdbool.h>
#include <string.h>
bool substringSearch(char *hay, char *needle) {
int m = strlen(hay) - strlen(needle);
for (int i = 0; i <= m; i++) {
bool found = true;
for (int j = 0; j < strlen(needle); j++) {
if (hay[i + j] != needle[j]) {
found = false;
break;
}
}
if (found) return true;
}
return false;
}
bool repeatedSubstringPattern(char* s) {
char* double_s = (char*)malloc(strlen(s) * 2 + 1);
strcpy(double_s, s);
strcat(double_s, s);
double_s[2 * strlen(s) - 1] = '\0';
bool result = substringSearch(double_s + 1, s);
free(double_s);
return result;
}public class Solution {
public bool RepeatedSubstringPattern(string s) {
string ss = s + s;
string temp = ss.Substring(1, ss.Length - 2);
return temp.Contains(s);
}
}The Python solution leverages the find function on a doubled string minus the first and last character to verify presence of original string, thereby inferring repetitive substrings.
Time Complexity: O(n). Space Complexity: O(n).
Approach 3: Default Approach
function repeatedSubstringPattern(s: string): boolean {
return (s + s).slice(1, (s.length << 1) - 1).includes(s);
}func repeatedSubstringPattern(s string) bool {
return strings.Index(s[1:]+s, s) < len(s)-1
}impl Solution {
pub fn repeated_substring_pattern(s: String) -> bool {
(s.clone() + &s)[1..s.len() * 2 - 1].contains(&s)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Repeated Substring using Substring Check | Time Complexity: O(n^2). Space Complexity: O(n). |
| Repeated Substring using Doubled String Trick | Time Complexity: O(n). Space Complexity: O(n). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Substring Length Check | O(n²) | O(1) | When implementing a straightforward brute-force solution or explaining the pattern logic during interviews |
| Doubled String Trick | O(n) | O(n) | Best general solution; efficient for large strings and commonly expected in interviews |
Frequently asked questions
Is Repeated Substring Pattern easy or hard?
LeetCode classifies Repeated Substring Pattern as an Easy problem. The brute-force solution is simple, but recognizing the doubled string trick requires a bit of pattern insight, which makes it a common interview warm-up for string manipulation.
Repeated Substring Pattern Python/Java solution
Both Python and Java solutions typically implement either substring-length enumeration or the doubled string trick. Python uses expressions like (s + s)[1:-1].contains(s), while Java uses substring and contains methods on the concatenated string.
How to solve Repeated Substring Pattern in O(n)?
Use the doubled string trick. Create a new string t = s + s, then remove the first and last characters and check if s exists inside that substring. If s appears, the original string must be composed of repeated substrings. Modern string search implementations allow this check in linear time.
What is the best approach for Repeated Substring Pattern?
The doubled string trick is the most efficient and elegant approach. Concatenate the string with itself (s + s), remove the first and last characters, and check if the original string appears inside. This works because repeating patterns create predictable rotations in the doubled string. The solution runs in O(n) time with O(n) space.
Is Repeated Substring Pattern asked at Google/Amazon/Meta?
Repeated substring and pattern detection problems appear frequently in interviews at companies like Amazon, Google, and Meta. The question tests understanding of string structure, pattern repetition, and clever transformations such as the doubled string technique.
What data structure is used in Repeated Substring Pattern?
The problem mainly uses string operations and substring search. No complex data structures are required. Efficient implementations rely on built-in string matching algorithms provided by standard libraries.
What is the time complexity of Repeated Substring Pattern?
The optimal solution using the doubled string trick runs in O(n) time because it performs a single substring search on a string of size about 2n. The simpler brute-force approach that checks every possible substring length can take O(n²) time due to repeated string comparisons.