LeetCode 459 - Repeated Substring Pattern

The problem asks us to determine whether a given string can be formed by repeating one of its substrings multiple times. In other words, we want to know if there exists some substring pattern such that concatenating that pattern repeatedly recreates the entire string exactly.

leetcodeeasystringstring-matching

LeetCode Problem 459

Difficulty: 🟢 Easy
Topics: String, String Matching

Solution

Problem Understanding

The problem asks us to determine whether a given string can be formed by repeating one of its substrings multiple times.

In other words, we want to know if there exists some substring pattern such that concatenating that pattern repeatedly recreates the entire string exactly.

For example, consider the string "abab":

  • The substring "ab" repeated twice becomes "abab"
  • Therefore, the answer is true

Now consider "aba":

  • Possible substrings are "a" and "ab"
  • Repeating "a" gives "aaa"
  • Repeating "ab" gives "abab"
  • Neither matches "aba"
  • Therefore, the answer is false

The input is a single string s containing only lowercase English letters. The maximum length is 10^4, which is small enough for quadratic solutions to technically pass, but efficient linear or near linear approaches are preferred.

An important detail is that the repeated substring must appear multiple times. The entire string itself does not count as the repeating unit unless it appears more than once.

Several edge cases are important:

  • A single character string can never satisfy the condition because there is no smaller substring to repeat.
  • Strings with all identical characters, such as "aaaa", should return true.
  • Strings whose length is prime often reduce the number of valid substring lengths.
  • Strings that almost repeat, such as "abababa", can trick naive implementations if partial matches are not handled carefully.

Approaches

Brute Force Approach

The brute force idea is to try every possible substring length that could divide the full string length evenly.

Suppose the string length is n. If a substring of length k forms the entire string by repetition, then:

  • k must divide n
  • The candidate substring is s[:k]
  • Repeating that substring n // k times should equal s

For each valid length:

  1. Extract the candidate substring
  2. Repeat it enough times
  3. Compare with the original string

If any candidate works, return true. Otherwise, return false.

This works because every possible repeating unit is explicitly tested. However, it repeatedly constructs strings and performs comparisons, making it less efficient than necessary.

Optimal Approach

The key observation is based on a clever string property.

If a string is composed of repeated patterns, then it will appear inside the string formed by:

(s + s)[1:-1]

Why does this work?

If the original string repeats a smaller pattern, shifting the doubled string by removing the first and last characters still leaves another occurrence of the original string inside.

For example:

s = "abab"

s + s = "abababab"

Remove first and last:
"bababa"

"abab" exists inside "bababa"

Now consider a non repeating string:

s = "aba"

s + s = "abaaba"

Remove first and last:
"baab"

"aba" does not exist inside "baab"

This gives a concise and elegant solution using substring search.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Tries every possible substring length
Optimal O(n) average, O(n²) worst case O(n) Uses doubled string pattern property

Algorithm Walkthrough

  1. Let the input string be s.
  2. Construct a new string by concatenating the string with itself.
doubled = s + s

This creates all possible cyclic shifts of the original string. 3. Remove the first and last characters from the doubled string.

trimmed = doubled[1:-1]

This step prevents the original string from trivially matching itself at the beginning or end. 4. Check whether the original string s exists inside trimmed.

s in trimmed
  1. If the substring exists, return true.

This means the string has an internal repeating structure. 6. Otherwise, return false.

Why it works

Suppose the string is built by repeating a substring pattern.

For example:

s = "abcabc"

When we concatenate the string with itself:

"abcabcabcabc"

The repeated structure causes shifted copies of the original string to appear internally. Removing the first and last characters still leaves one of these shifted copies intact.

If the string does not have a repeating structure, no internal occurrence of the full string exists after trimming.

This property guarantees correctness.

Python Solution

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        doubled = s + s
        trimmed = doubled[1:-1]
        
        return s in trimmed

The implementation follows the optimal observation directly.

First, the string is duplicated using s + s. This creates a larger string containing all cyclic shifts of the original pattern.

Next, the first and last characters are removed. Without this step, every string would trivially appear inside its own doubled version.

Finally, Python's substring search operator checks whether the original string exists inside the trimmed result.

If it does, the string must consist of a repeating substring pattern.

Go Solution

package main

import "strings"

func repeatedSubstringPattern(s string) bool {
    doubled := s + s
    trimmed := doubled[1 : len(doubled)-1]

    return strings.Contains(trimmed, s)
}

The Go implementation mirrors the Python logic closely.

The main difference is that Go uses the strings.Contains function instead of Python's in operator.

String slicing in Go uses index ranges, so:

doubled[1 : len(doubled)-1]

removes the first and last characters.

There are no overflow concerns because the input size is small. Go strings are immutable, just like Python strings.

Worked Examples

Example 1

Input: s = "abab"

Step 1: Double the string

Variable Value
doubled "abababab"

Step 2: Remove first and last characters

Variable Value
trimmed "bababa"

Step 3: Check containment

Check Result
"abab" in "bababa" true

Final answer:

true

Example 2

Input: s = "aba"

Step 1: Double the string

Variable Value
doubled "abaaba"

Step 2: Remove first and last characters

Variable Value
trimmed "baab"

Step 3: Check containment

Check Result
"aba" in "baab" false

Final answer:

false

Example 3

Input: s = "abcabcabcabc"

Step 1: Double the string

Variable Value
doubled "abcabcabcabcabcabcabcabc"

Step 2: Remove first and last characters

Variable Value
trimmed "bcabcabcabcabcabcabcab"

Step 3: Check containment

Check Result
"abcabcabcabc" in trimmed true

Final answer:

true

Complexity Analysis

Measure Complexity Explanation
Time O(n) average, O(n²) worst case Depends on substring search implementation
Space O(n) The doubled string requires additional memory

The dominant cost comes from constructing the doubled string and performing substring search.

Most modern substring search implementations are highly optimized and effectively linear for practical inputs. The extra space comes from storing the concatenated string.

Test Cases

sol = Solution()

assert sol.repeatedSubstringPattern("abab") == True      # basic repeating pattern
assert sol.repeatedSubstringPattern("aba") == False      # not repeatable
assert sol.repeatedSubstringPattern("abcabcabcabc") == True  # longer repeating pattern

assert sol.repeatedSubstringPattern("a") == False        # single character
assert sol.repeatedSubstringPattern("aa") == True        # smallest valid repetition
assert sol.repeatedSubstringPattern("aaa") == True       # repeated single character
assert sol.repeatedSubstringPattern("abcd") == False     # no repetition

assert sol.repeatedSubstringPattern("ababab") == True    # repeating "ab"
assert sol.repeatedSubstringPattern("abcabc") == True    # repeating "abc"
assert sol.repeatedSubstringPattern("abcab") == False    # partial repetition only

assert sol.repeatedSubstringPattern("zzzzzz") == True    # all identical characters
assert sol.repeatedSubstringPattern("xyzxyzxyz") == True # repeated larger unit
assert sol.repeatedSubstringPattern("xxyxxy") == True    # repeated "xxy"

assert sol.repeatedSubstringPattern("abababa") == False  # almost repeating
assert sol.repeatedSubstringPattern("abac") == False     # mixed characters
Test Why
"abab" Standard repeating pattern
"aba" Non repeating string
"abcabcabcabc" Multiple valid repeating units
"a" Single character edge case
"aa" Smallest repeating string
"aaa" Repeated single character
"abcd" Completely unique characters
"ababab" Even length repeated pattern
"abcabc" Repeated length 3 substring
"abcab" Partial repetition should fail
"zzzzzz" Identical character repetition
"xyzxyzxyz" Larger repeating block
"xxyxxy" Non trivial repeating substring
"abababa" Near match that should fail
"abac" Irregular pattern

Edge Cases

Single Character Strings

A string with length 1 cannot possibly be formed by repeating a smaller substring multiple times. This is a common source of bugs because some implementations accidentally allow the full string itself as a valid repeating unit.

For example:

"a"

The algorithm correctly returns false because "a" does not appear inside:

("a" + "a")[1:-1]

which becomes an empty string.

Strings With All Identical Characters

Strings like "aaaaaa" can be formed using multiple different substring sizes:

  • "a" repeated 6 times
  • "aa" repeated 3 times
  • "aaa" repeated 2 times

Some naive implementations incorrectly stop after checking only one candidate size. The doubled string approach naturally handles all possibilities simultaneously.

Partial Repetition

Strings such as "abababa" look repetitive but are not exact repetitions of a smaller substring.

This is important because naive implementations sometimes only compare prefixes without ensuring the entire string is covered evenly.

The algorithm avoids this issue because containment inside the trimmed doubled string only occurs for fully repeatable structures.