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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Repeated Substring Pattern

Number: 459

Difficulty: Easy

Paid? No

Companies: Amazon, Google, Bloomberg, Myntra, Apple, eBay, Adobe

Problem Description

Determine if a given string can be constructed by taking a substring of it and appending multiple copies of that substring together.

Key Insights

  • The repeated substring must be a divisor of the entire string's length.
  • A trick uses string manipulation by checking if the string exists in (s+s) with its first and last characters removed.
  • Alternatively, iterate through all possible substring lengths (that are divisors of the total length) and check if repeating the substring yields the original string.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case if checking each possible candidate manually, but the trick method runs in O(n).
Space Complexity: O(n) due to the extra temporary string created in the trick method.

Solution

We can solve the problem using one of two approaches:

  1. Brute-force: Try each possible substring whose length divides the original string length. For each candidate, repeat it and compare with the original string.
  2. Trick approach: Form a new string by concatenating the original string with itself and remove the first and last characters. Then check if the original string exists in this modified string. If it does, the original string is composed of repeated substrings.

The trick approach is more elegant and efficient. It leverages the fact that a repeated pattern will appear at least twice in the overlapped string.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

# Function to check if the string can be constructed by repeated substring pattern
def repeatedSubstringPattern(s: str) -> bool:
    # Create a new string by concatenating s with itself and removing first and last characters
    doubled_s = (s + s)[1:-1]
    # Check if the original string s is present in the modified string
    return s in doubled_s

# Example usage:
if __name__ == "__main__":
    test_string = "abcabc"
    print(repeatedSubstringPattern(test_string))  # Expected output: True
← Back to All Questions