Problem Description

You are given a string s. Your task is to determine whether this string can be formed by taking a substring of it and repeating that substring multiple times.

For example:

• The string "abab" can be constructed by repeating the substring "ab" twice
• The string "abcabcabc" can be constructed by repeating the substring "abc" three times
• The string "aba" cannot be constructed by repeating any substring

The solution uses a clever trick: when you concatenate the string with itself (s + s) and then search for the original string starting from index 1, if the string can be formed by repeating a pattern, you'll find it before reaching the length of the original string.

Here's why this works:

• If s = "abab", then s + s = "abababab"
• Looking for "abab" starting from index 1, we find it at index 2
• Since 2 < 4 (length of original string), the pattern exists

The key insight is that if a string is made of repeated patterns, when doubled, the original string will appear again before the midpoint because the pattern "bridges" across where the two copies meet.

Intuition

Let's think about what happens when a string is made of repeated patterns. If s consists of a pattern p repeated k times (where k ≥ 2), then s = p + p + ... + p (k times).

Now, what happens when we concatenate s with itself? We get s + s = p + p + ... + p + p + p + ... + p (2k times).

The crucial observation is that if we start looking for s within s + s from index 1 (not index 0), we're essentially shifting our view by one character. If s has a repeating pattern, this shift will cause the patterns to "realign" at some point before we reach the middle of the concatenated string.

For instance, with s = "abcabc" (pattern "abc" repeated twice):

• s + s = "abcabcabcabc"
• Starting from index 1: "bcabcabcabc"
• Starting from index 2: "cabcabcabc"
• Starting from index 3: "abcabcabc" ← Here we find s again!

The reason we find s at index 3 (which is less than len(s) = 6) is because the repeating structure allows the pattern to "wrap around" and reconstruct the original string.

On the other hand, if there's no repeating pattern (like s = "abcd"):

• s + s = "abcdabcd"
• The only place we'll find "abcd" is at index 0 and index 4
• Since we start searching from index 1, we'll find it at index 4, which equals len(s)

This leads to the elegant one-liner: (s + s).index(s, 1) < len(s). If the index where we find s is less than the length of s, then s must have a repeating pattern.

Solution Approach

The implementation is remarkably concise, using Python's built-in string methods to solve the problem in a single line:

def repeatedSubstringPattern(self, s: str) -> bool:
    return (s + s).index(s, 1) < len(s)

Let's break down how this works step by step:

1. String Concatenation: First, we create a new string by concatenating s with itself: s + s. This doubles the original string.

2. Finding the Index: We use the index() method to find the first occurrence of the original string s within the concatenated string, but crucially, we start the search from index 1 (not 0). The syntax (s + s).index(s, 1) means "find s in (s + s) starting from position 1".

3. Comparison: We check if this index is less than len(s).

   • If the index is less than len(s), it means we found the original string before reaching the halfway point of the concatenated string, indicating a repeating pattern exists.
   • If the index equals len(s), it means the first occurrence of s (after skipping index 0) is at the second copy, indicating no repeating pattern.

Time Complexity: O(n) where n is the length of the string, as the index() method performs a linear search.

Space Complexity: O(n) for creating the concatenated string s + s.

The beauty of this solution lies in leveraging the property that a string with a repeating pattern will "reconstruct" itself when shifted by any multiple of the pattern length, which is exactly what happens when we search for s in s + s starting from index 1.

Example Walkthrough

Let's walk through the solution with the string s = "abcabc".

Step 1: Concatenate the string with itself

• s + s = "abcabc" + "abcabc" = "abcabcabcabc"

Step 2: Search for the original string starting from index 1

• We're looking for "abcabc" in "abcabcabcabc" starting from position 1
• Let's check each position:
  • Index 1: "bcabca..." - doesn't match "abcabc"
  • Index 2: "cabcab..." - doesn't match "abcabc"
  • Index 3: "abcabc..." - matches! We found "abcabc" at index 3

Step 3: Compare the index with the original string length

• Found index: 3
• Original string length: 6
• Is 3 < 6? Yes!
• Therefore, the string CAN be formed by repeating a pattern (in this case, "abc" repeated twice)

Counter-example with a non-repeating string:

Let's try s = "abcde" (no repeating pattern).

Step 1: s + s = "abcde" + "abcde" = "abcdeabcde"

Step 2: Search for "abcde" starting from index 1:

• Index 1: "bcdea..." - doesn't match
• Index 2: "cdeab..." - doesn't match
• Index 3: "deabc..." - doesn't match
• Index 4: "eabcd..." - doesn't match
• Index 5: "abcde" - matches! Found at index 5

Step 3: Compare:

• Found index: 5
• Original string length: 5
• Is 5 < 5? No!
• Therefore, the string CANNOT be formed by repeating a pattern

The key insight: when a repeating pattern exists, the string "reconstructs" itself before reaching its original length in the doubled string, but when no pattern exists, you only find it at exactly the length position (which is the start of the second copy).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the string s.

The algorithm concatenates the string s with itself, creating a string of length 2n. Then it uses the index() method to search for the first occurrence of s starting from position 1. The index() method internally uses an efficient string searching algorithm (typically a variant of Boyer-Moore or similar), which has an average time complexity of O(n) for finding a pattern of length n in a text of length 2n.

Space Complexity: O(n) where n is the length of the string s.

The space complexity comes from creating the concatenated string s + s, which requires O(2n) = O(n) additional space. The index() method itself typically uses O(1) or at most O(n) auxiliary space depending on the implementation, but the dominant factor is the space needed for the concatenated string.

Common Pitfalls

1. IndexError with Empty Strings

The index() method raises a ValueError when the substring is not found. While this isn't typically an issue for this problem (since s will always be found in s + s), edge cases with empty strings or single characters need careful consideration.

Pitfall Example:

def repeatedSubstringPattern(self, s: str) -> bool:
    # This could potentially fail with certain edge cases
    return (s + s).index(s, 1) < len(s)

Solution:

def repeatedSubstringPattern(self, s: str) -> bool:
    if len(s) <= 1:
        return False
    return (s + s).index(s, 1) < len(s)

2. Using find() Instead of index() Without Proper Handling

Some developers might use find() instead of index() to avoid exceptions, but forget that find() returns -1 when the substring is not found, which can lead to incorrect logic.

Pitfall Example:

def repeatedSubstringPattern(self, s: str) -> bool:
    # Wrong! If s is not found, find() returns -1, which is < len(s)
    return (s + s).find(s, 1) < len(s)

Solution:

def repeatedSubstringPattern(self, s: str) -> bool:
    position = (s + s).find(s, 1)
    return position != -1 and position < len(s)

3. Forgetting the Starting Index Parameter

A critical mistake is omitting the starting index parameter in the search method, which would always return 0 (finding the string at the beginning).

Pitfall Example:

def repeatedSubstringPattern(self, s: str) -> bool:
    # Wrong! This will always find s at index 0
    return (s + s).index(s) < len(s)  # Always returns True!

Solution:

def repeatedSubstringPattern(self, s: str) -> bool:
    # Correct: Start searching from index 1
    return (s + s).index(s, 1) < len(s)

4. Misunderstanding the Algorithm's Logic

Some might try to "optimize" by searching in a substring of the doubled string, missing valid patterns.

Pitfall Example:

def repeatedSubstringPattern(self, s: str) -> bool:
    # Wrong! This limits the search space incorrectly
    doubled = s + s
    return s in doubled[1:len(s)]  # Misses some valid patterns

Solution:

def repeatedSubstringPattern(self, s: str) -> bool:
    # Correct: Search in the full doubled string starting from index 1
    doubled = s + s
    return s in doubled[1:-1]  # Or use the index method as shown

5. Alternative Implementation Using Slicing

While not a pitfall per se, using string slicing with the in operator is another valid approach that some find more readable:

def repeatedSubstringPattern(self, s: str) -> bool:
    # Alternative: Check if s appears in the "middle" of s+s
    return s in (s + s)[1:-1]

This avoids the index comparison and is equally efficient, though it creates an additional substring which slightly increases space usage.