459. Repeated Substring Pattern

459

EasyTrie and Advanced String SearchString manipulation (with KMP as the classic alternative)Rotation-search / string doubling

Repeated Substring Pattern

Given a string s, return true if it can be constructed by taking some substring of it and concatenating multiple (two or more) copies of that substring together.

Open official problem prompt ↗

In plain English

Decide whether the whole string is just one smaller block copied end to end two or more times.

Picture it like this

Like checking whether a bracelet pattern is one motif stamped repeatedly: rotate the bracelet by less than a full turn and see if it lands on itself.

Example

Input: s = "abab"
Output: true
Why: "abab" is "ab" repeated twice.

Constraints

1 <= s.length <= 10^4s consists of lowercase English letters

Pattern lesson

See the pattern, then code

Rotation-search / string doubling

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. If s is a repeat of a block, then s is a non-trivial rotation of itself; concatenating s+s and searching for s in the interior (excluding the first and last character) reveals that rotation exactly when s is periodic.

New words, made simpleKnow these before the algorithm

Period: The length of the repeating block that tiles the string.
Rotation: Shifting characters cyclically; a periodic string maps onto itself under a rotation smaller than its length.
KMP failure function: The classic O(n) alternative that finds the longest proper prefix that is also a suffix, revealing the period.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Try every divisor

Works and is intuitive but does redundant comparisons.

For each block length d dividing n, check if repeating s[:d] rebuilds s.

Time O(n * d(n))Space O(n)

Best choiceDoubling trick

One line, linear, and captures periodicity via self-rotation.

Check whether s occurs in (s+s)[1:-1].

Time O(n)Space O(n)

The rule we keep true

Invariant

s appears in (s+s)[1:-1] if and only if s has a proper period, i.e. equals a block repeated two or more times.

Why this is correct

Reasoning

If s = block^k with k >= 2, then s+s contains a copy of s starting at offset len(block), which lies strictly inside the trimmed range; conversely, a match at offset p (1 <= p < n) forces s to be periodic with period p that must divide n.

The algorithm in three movesSay these aloud before coding

1Concatenate s with itself to form s + s

s+s = 'abababab'

2Strip the first and last character to block trivial full-string matches

trim [1:-1] = 'bababa'

3Search for s inside the trimmed string

'abab' found at index 1

4Return true if a match is found

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Reads='abab'

2 · AskForm s+s?

3 · Update state'abababab'

4 · Resultlength 8

Key takeaway

The block 'ab' (indices 0-1) repeats to build 'abab'.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3The whole solution
(s+s)[1:-1].find(s) removes the two trivial matches at the ends and reports any interior occurrence.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single character 'a' returns false (needs two or more copies)
String of identical characters like 'aaaa' returns true
No repetition like 'abcd' returns false
Two-character repeat 'aa' returns true

Common beginner mistakes

Forgetting to trim both ends, which would always find s at position 0
Assuming only lengths that are half of n; the period can be any divisor
Off-by-one in the slice [1:-1]
Overcomplicating with divisor loops when the one-liner suffices

Check your understanding

Why remove exactly one character from each end before searching?

Repeated Substring Pattern

Repeated Substring Pattern

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search