We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Repeated Substring Pattern

Difficulty: Easy

Problem Description

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Key Insights

  • The string can be constructed from a substring if its length is divisible by the length of the substring.
  • By concatenating the string with itself and removing the first and last characters, we can check if the original string exists in this new string.
  • The approach leverages the properties of substrings and string repetition to efficiently determine the result.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves checking if the string can be formed by repeating a substring. We can concatenate the string with itself and check if the original string appears in the concatenated version (excluding the first and last characters). If it does, then the original string can be constructed by repeating a substring.

The algorithmic approach uses:

  • String manipulation to create a new string.
  • Searching within the new string to find the original string.

Code Solutions

def repeatedSubstringPattern(s: str) -> bool:
    # Concatenate the string with itself and remove the first and last characters
    doubled = (s + s)[1:-1]
    # Check if the original string exists in the modified string
    return s in doubled
← Back to All Questions