Repeated Substring Pattern - Video Solutions
LeetCode 459. Repeated Substring Pattern (Algorithm Explained)
Repeated Substring Pattern - Video Solution
Watch 10 video solutions for Repeated Substring Pattern, a easy level problem involving String, String Matching. This walkthrough by Nick White has 44,976 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 |