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.In #459 Repeated Substring Pattern, the goal is to determine whether a given string can be formed by repeating one of its substrings multiple times. A key observation is that if a string is built from a repeating unit, certain string matching patterns will appear when the string is combined with itself.
One common strategy is to use a clever string doubling trick. By concatenating the string with itself and searching for the original string within this new string (excluding the first and last characters), you can detect whether a repeating pattern exists. If the original string appears again inside this modified range, it means the string is composed of repeated substrings.
Another more formal method uses string matching algorithms such as the KMP (Knuth–Morris–Pratt) prefix table to identify repeating prefix-suffix structures. Both approaches rely on analyzing repeated patterns within the string efficiently, resulting in linear-time solutions.
These strategies allow the problem to be solved efficiently without brute-force checking of all possible substrings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| String Doubling + Substring Search | O(n) | O(n) |
| KMP Prefix Function (String Matching) | O(n) | O(n) |
Nick White
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.
Time Complexity: O(n^2). Space Complexity: O(n).
1def repeatedSubstringPattern(s):
2 n = len(s)
3 for i in range(1, n // 2 + 1):
4 if n % i == 0:
5 if s[:i] * (n // i) == s:
6 return True
7 return FalseThe 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.
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.
Time Complexity: O(n). Space Complexity: O(n).
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is commonly used in coding interviews to test understanding of string manipulation and pattern detection. Interviewers may expect candidates to recognize the string doubling trick or use a prefix table approach.
Yes, you can check every possible substring length and verify if repeating it forms the original string. However, this brute-force approach is less efficient compared to optimized string matching techniques like KMP or the concatenation trick.
A common optimal approach is the string doubling trick where the string is concatenated with itself and the original string is searched within the modified range. If it appears again inside the combined string, it indicates the original string is built from a repeating substring. This approach runs in linear time.
String matching algorithms like the KMP (Knuth–Morris–Pratt) algorithm are well suited for this problem. KMP helps identify repeating prefix-suffix patterns efficiently, which can reveal whether the string is constructed from a repeating unit.
In C, we manually concatenate the string and utilize a helper function for substring search within the modified doubled string to ascertain repetition.