459. Repeated Substring Pattern
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 43.3%
Problem Breakdown
The problem asks us to determine if a given string s can be constructed by repeating a substring of itself multiple times. The input is a single string s, and the output should be a boolean indicating whether such a construction is possible.
Inputs:
- A single string
sconsisting of lowercase English letters.
Outputs:
- A boolean value (
trueorfalse) indicating whether the string can be constructed by repeating a substring.
Implicit Constraints:
- The length of the string
sis between 1 and 10,000 characters. - The string consists only of lowercase English letters.
Tricky Edge Cases:
- An empty string (though not explicitly mentioned in constraints, it’s worth considering).
- Strings that are already a single repeated character (e.g., “aaa”).
- Strings where no substring can be repeated to form the original string.
Intuition
A brute-force approach would involve checking all possible substrings of s to see if repeating any of them forms the original string. This approach is inefficient because it has a time complexity of O(n^2) due to nested loops for generating and checking substrings.
The key insight is that if a string can be constructed by repeating a substring, then the length of this substring must divide the total length of s evenly. Additionally, we can concatenate the string with itself and check if the original string appears as a substring in this new string (excluding the first and last characters). This approach leverages the properties of string rotations and reduces the time complexity to O(n).
Approach
- Concatenate the String: Create a new string by concatenating
swith itself. - Check for Substring: Check if the original string
sappears as a substring in this concatenated string, excluding the first and last characters. - Return Result: If
sis found as a substring in the modified string, returntrue; otherwise, returnfalse.
This approach works because if s can be constructed by repeating a substring, then the repeated pattern will appear within the concatenated string.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string
s. This is because we perform a single substring search operation on the concatenated string. - Space Complexity: O(n), due to the creation of the concatenated string which has a length of 2n.
Solution
def repeatedSubstringPattern(s: str) -> bool:
# Concatenate s with itself and check if s is a substring in the new string (excluding first and last characters)
return s in (s + s)[1:-1]
Edge Cases Handled
- Single Character Strings: The approach naturally handles strings of length 1, as they cannot be constructed by repeating a substring.
- Strings with Repeated Characters: The approach correctly identifies strings like “aaa” as having a repeated pattern.
- Non-Repeating Strings: Strings that cannot be formed by repeating any substring will return
false. - Empty String: While not explicitly mentioned in constraints, the approach handles an empty string by returning
false, as it cannot be constructed by repeating any substring.