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.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.
C
C++
Java
C#
JavaScript
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.
C
C++
Java
C#
JavaScript
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). |
LeetCode 459. Repeated Substring Pattern (Algorithm Explained) • Nick White • 42,256 views views
Watch 9 more video solutions →Practice Repeated Substring Pattern with our built-in code editor and test cases.
Practice on FleetCode