Repeated Substring Pattern · Optimal Solution

Double, trim, and search.

A genome sequencer checks whether a DNA fragment is built by repeating a shorter motif — like "ATGATG" being two copies of "ATG". Given any string, determine whether it can be constructed by repeating a substring two or more times. The elegant trick: concatenate the string with itself, remove the boundary characters, and check whether the original still appears inside. O(n) time. O(n) space.

Interactive

Watch the doubled string reveal the pattern

Concept

Why doubling exposes repetition

The doubled-and-trimmed trick reduces a structural question about periodicity to a simple substring search.

the doubling trick

If s is made of repeated copies of a pattern p, then s + s creates overlapping copies where a new occurrence of s appears at an offset equal to p.length — inside the doubled string, not at the boundary.

why trimming works

The original s trivially appears at position 0 and position n in the doubled string. Removing the first and last character eliminates exactly these two trivial anchors without destroying any internal alignment.

false positives are impossible

If s is not periodic, every candidate window in the trimmed string straddles the junction between the two copies, breaking the match. The search correctly returns false.

Algorithm

Three operations, one answer

No loop over divisors. No pattern matching setup. Just concatenation, trimming, and a single search.

  1. 1

    Concatenate the string with itself

    Build doubled = s + s. This creates a string of length 2n containing two adjacent copies.

  2. 2

    Remove the first and last character

    Set trimmed = doubled[1..^1]. This removes the trivial match at position 0 and the one at position n.

  3. 3

    Search for the original inside

    If trimmed.contains(s) is true, the string is built from a repeated substring. Otherwise it is not.

Edge Cases

Where the answer is immediate

Some inputs resolve before the search even starts.

Single character

The doubled string has only two characters. After trimming, nothing remains to search — the result is always false. A single character has no proper substring to repeat.

All identical characters

Strings like "aaaa" match at the very first candidate position. Every character is a repetition of one, so the search succeeds immediately.

Prefix overlap without full repetition

Strings like "abcab" share structure between prefix and suffix, but cannot be decomposed into complete copies of any substring. Every candidate window fails.