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 <= 104s consists of lowercase English letters.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.
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.
Time Complexity: O(n^2). Space Complexity: O(n).
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.
Time Complexity: O(n). Space Complexity: O(n).
| 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 | — |
| 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 |
LeetCode 459. Repeated Substring Pattern (Algorithm Explained) • Nick White • 44,500 views views
Watch 9 more video solutions →Practice Repeated Substring Pattern with our built-in code editor and test cases.
Practice on FleetCode