LeetCode 459: Repeated Substring Pattern

Problem Restatement

We are given a string s.

We need to check whether s can be constructed by taking a non-empty substring and repeating it multiple times. The substring must be shorter than the whole string, because repeating the entire string once does not count. The official problem asks whether s can be built by appending multiple copies of a substring together.

For example:

s = "abab"

This can be made by repeating "ab" twice:

"ab" + "ab" = "abab"

So the answer is:

True

Input and Output

Function shape:

def repeatedSubstringPattern(s: str) -> bool:
    ...

Examples

Example 1:

s = "abab"

The substring "ab" repeated twice gives:

"abab"

Answer:

True

Example 2:

s = "aba"

Possible proper substrings are:

"a"
"ab"

Repeating "a" gives strings like "aa" or "aaa".

Repeating "ab" gives strings like "abab".

Neither gives "aba".

Answer:

False

Example 3:

s = "abcabcabcabc"

This can be made by repeating "abc" four times:

"abc" + "abc" + "abc" + "abc"

It can also be made by repeating "abcabc" twice.

Answer:

True

First Thought: Try Every Substring Length

A direct approach is to try every possible length for the repeated substring.

If n = len(s), then the repeated substring length must be less than n.

Also, the length must divide n.

For example, if:

s = "abcabcabcabc"
n = 12

valid candidate lengths are:

1, 2, 3, 4, 6

Length 3 works because:

"abc" * 4 == "abcabcabcabc"

Brute force code:

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)

        for length in range(1, n):
            if n % length != 0:
                continue

            pattern = s[:length]
            if pattern * (n // length) == s:
                return True

        return False

This is simple and correct.

Problem With Brute Force

The brute force method may build many repeated strings.

For every candidate length, it may compare up to n characters.

In the worst case, this costs about:

O(n^2)

For this problem, that can still pass in many languages because the constraints are moderate, but there is a cleaner string trick.

Key Insight

If s is made by repeating a smaller pattern, then s appears inside the middle of:

s + s

after removing the first and last character.

For example:

s = "abab"
s + s = "abababab"

Remove the first and last character:

"bababa"

The original string "abab" appears inside "bababa".

Why?

Because repeated strings remain unchanged under some rotation.

For "abab", shifting left by two characters still gives "abab":

"abab" -> "abab"

That shift appears naturally inside s + s.

For a non-repeated string like:

s = "aba"

we get:

s + s = "abaaba"
(s + s)[1:-1] = "baab"

The original "aba" does not appear inside "baab".

So the condition is:

s in (s + s)[1:-1]

Algorithm

Build the doubled string:

doubled = s + s

Remove the first and last character:

middle = doubled[1:-1]

Return whether s appears in middle:

return s in middle

This works because we exclude the two trivial matches:

A match inside the middle means there is a non-trivial rotation equal to s, which happens exactly when s has a repeated substring pattern.

Correctness

If s is made by repeating a substring p, then:

s = p + p + ... + p

with at least two copies.

Shifting s left by len(p) characters gives the same string again, because the blocks are identical.

This shifted copy of s appears inside s + s, starting at index len(p).

Since 0 < len(p) < len(s), this occurrence is inside (s + s)[1:-1].

So the algorithm returns True.

Now suppose the algorithm returns True.

Then s appears inside (s + s)[1:-1], which means there is a shift k where:

0 < k < len(s)

and rotating s by k positions gives the same string.

A string equal to one of its non-trivial rotations must be periodic. Its repeating unit length divides the string into identical blocks.

Therefore, s can be built by repeating a smaller substring.

So the algorithm returns True exactly for strings with a repeated substring pattern.

Complexity

Let n = len(s).

A more conservative theoretical bound for generic substring search is O(n^2), depending on the language and search implementation.

Implementation

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

Code Explanation

The expression:

s + s

creates two copies of the string.

For example:

"abab" + "abab" = "abababab"

The slice:

[1:-1]

removes the first and last character.

This prevents matching the original string at the obvious positions.

Then:

s in (s + s)[1:-1]

checks whether the original string appears at a non-trivial shifted position.

If it does, s has a repeated substring pattern.

Alternative Implementation: Divisor Check

This version is more explicit and useful for learning.

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)

        for length in range(1, n // 2 + 1):
            if n % length != 0:
                continue

            pattern = s[:length]
            if pattern * (n // length) == s:
                return True

        return False

We only need to check lengths up to n // 2, because the repeated substring must appear at least twice.

Testing

def run_tests():
    s = Solution()

    assert s.repeatedSubstringPattern("abab") is True
    assert s.repeatedSubstringPattern("aba") is False
    assert s.repeatedSubstringPattern("abcabcabcabc") is True
    assert s.repeatedSubstringPattern("a") is False
    assert s.repeatedSubstringPattern("aaaa") is True
    assert s.repeatedSubstringPattern("abac") is False
    assert s.repeatedSubstringPattern("xyzxyz") is True
    assert s.repeatedSubstringPattern("zzzzzz") is True

    print("all tests passed")

run_tests()

Test meaning: