Domain 1EasyCORE

Repeated Substring Pattern

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

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 s consisting of lowercase English letters.

Outputs:

  • A boolean value (true or false) indicating whether the string can be constructed by repeating a substring.

Implicit Constraints:

  • The length of the string s is 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

  1. Concatenate the String: Create a new string by concatenating s with itself.
  2. Check for Substring: Check if the original string s appears as a substring in this concatenated string, excluding the first and last characters.
  3. Return Result: If s is found as a substring in the modified string, return true; otherwise, return false.

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.