Repeated Substring Pattern - Solution & Explanation
Problem Statement
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.
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.
Complexity
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.
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.
Complexity
Time Complexity: O(n). Space Complexity: O(n).
Approach 3: Default Approach
Try this approach in the editor →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 | — |
Detailed 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 |
Video Solution
LeetCode 459. Repeated Substring Pattern (Algorithm Explained) • Nick White • 44,976 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Repeated Substring Pattern easy or hard?
Repeated Substring Pattern Python/Java solution
How to solve Repeated Substring Pattern in O(n)?
What is the best approach for Repeated Substring Pattern?
Is Repeated Substring Pattern asked at Google/Amazon/Meta?
What data structure is used in Repeated Substring Pattern?
What is the time complexity of Repeated Substring Pattern?
Ready to solve this problem?
Practice Repeated Substring Pattern with our built-in code editor and test cases.
Practice on FleetCode