Repeated Substring Pattern: The Double String Trick
LeetCode Repeated Substring Pattern (problem 459) asks you to determine whether a given string s can be formed by repeating a substring of itself two or more times. For example, "abcabc" returns true because it is "abc" repeated twice, while "aba" returns false because no substring can be repeated to produce it.
The problem
Given a string s, return true if it can be constructed by taking a substring and appending multiple copies of that substring together.
Why this problem matters
Repeated Substring Pattern is a gateway to thinking about string periodicity. The brute-force approach of testing every possible substring length works, but it misses the deeper structure. The elegant one-liner solution teaches you a powerful property of periodic strings that shows up in KMP preprocessing, string hashing, and pattern matching. Once you see the trick, you start recognizing similar "construct and search" strategies across many problems.
The key insight
Here is the core idea: if s is made of a repeating unit, then when you concatenate s with itself to form s + s, there will be an extra copy of s hiding in the middle. To make sure you are not just finding the original copies at the start and end, you remove the first and last character of the doubled string. If you can still find s inside this trimmed version, then s must have a repeating pattern.
Why does removing those two characters work? The first character of s + s is the start of the "left" copy, and the last character is the end of the "right" copy. By chopping them off, you break both of those original copies. Any surviving occurrence of s must straddle the boundary, which only happens when s has internal periodicity.
In Python, this translates to a single expression: s in (s + s)[1:-1].
The code
def repeatedSubstringPattern(s):
return s in (s + s)[1:-1]
Why this works
Suppose s has length n and is composed of a substring t of length k, repeated n / k times. Then s + s has length 2n and contains 2n / k copies of t. When you remove the first and last character, you break exactly the first and last copy of t (partially). But because there are 2n / k copies total and 2n / k >= 4 (since n / k >= 2), there are enough complete copies of t left in the middle to form at least one full copy of s.
Conversely, if s has no repeating unit, then the only places where s appears in s + s are at index 0 and index n. Removing the first and last character destroys both of those occurrences, so s will not be found.
This gives you a clean if-and-only-if condition: s appears in (s + s)[1:-1] exactly when s is built from a repeated substring.
Visual walkthrough
Walk through s = "abcabc" step by step. Watch how the doubled string, after trimming, still contains a full copy of s in the interior.
Step 1: Start with s
The original string s = "abcabc". We want to know if it is built from a repeated substring.
Step 2: Double the string (s + s)
Concatenate s with itself: "abcabcabcabc". If s has a repeating unit, copies of s overlap inside this doubled string.
Step 3: Remove first and last character
Strip index 0 and index 11. This breaks the original copy at the start and end, but if a repeating pattern exists, a full copy of s still survives in the middle.
Step 4: Search for s in the modified string
Found "abcabc" starting at index 3 (green). Since s appears inside the trimmed doubled string, s is made of a repeated pattern.
The match at positions 3 through 8 confirms the repeating pattern. If you try this with "aba", doubling gives "abaaba", trimming to "baab", and searching for "aba" fails. No match, no repeating pattern.
Complexity analysis
| Metric | Value |
|---|---|
| Time | O(n) to O(n^2), depending on the substring search implementation |
| Space | O(n), for the concatenated string |
Python's in operator uses a fast substring search (a variant of Boyer-Moore-Horspool), which runs in O(n) on average. The concatenated string s + s has length 2n, so the search operates on a string of that size. In the worst case, substring search can degrade to O(n^2), but this is rare with typical inputs. The space cost comes from constructing the 2n-length string.
Building blocks
String concatenation as a structural probe
Doubling a string and searching for the original is a reusable technique. It works because concatenation creates overlap zones that reveal internal periodicity. The same idea appears in problems involving cyclic rotations: if you want to check whether string b is a rotation of string a, you can check if b appears in a + a.
Substring search
The in operator (or find, or indexOf in other languages) is doing the heavy lifting. Knowing that Python's built-in search is efficient lets you write a one-liner without worrying about performance. In interviews, you might be asked to explain what algorithm runs under the hood or to implement KMP as a follow-up.
Edge cases
- Single character.
"a"returnsfalse. You need at least two repetitions, and a single character cannot be split into a repeated substring. - Two identical characters.
"aa"returnstrue. The substring"a"repeats twice. - All same characters.
"aaaa"returnstrue. The substring"a"repeats four times (or"aa"repeats twice). - Almost repeating.
"abcabd"returnsfalse. The last character breaks the pattern. - Odd-length non-repeating.
"abcab"returnsfalse. No substring length divides 5 to produce a valid repetition (other than length 1, and the characters are not all the same). - Long repeating unit.
"abcdabcd"returnstrue. The unit"abcd"has length 4 and repeats twice in a string of length 8.
From understanding to recall
The beauty of this problem is the gap between "hard to figure out" and "easy to remember." Once you see the double-and-trim trick, you will never forget it. But getting there on your own under interview pressure is a different story. The way to bridge that gap is deliberate practice.
Write the one-liner from memory. Then write the brute-force version that tests each possible substring length from 1 to n / 2. Compare them. Understand why both are correct. Then space out your reviews so the elegant solution becomes your default instinct when you see anything related to string periodicity.