Repeated Substring Pattern is a classic string problem that shows up often in coding interviews because it tests how well you understand string structure, pattern detection, and efficient searching. The problem is simple to state but surprisingly easy to overcomplicate if you jump straight into brute force.
You’re given a non-empty string, and you need to determine whether it can be constructed by repeating one of its substrings multiple times. In other words, the question is:
Can this string be formed by taking a smaller piece and repeating it end-to-end until it matches the original string exactly?
For example, a string like "abab" can be formed by repeating "ab" twice. Similarly, "aaaa" can be formed by repeating "a" four times. But a string like "abac" cannot be formed by repeating a single substring.
This problem matters in interview prep because it checks multiple skills at once. It tests whether you can reason about patterns and periodicity in strings, whether you can avoid inefficient substring checking, and whether you understand the difference between a correct approach and a scalable one.
Why brute force approaches are tempting (and risky)
A typical first attempt is to test every possible substring length, repeat it, and see if it matches the full string. Conceptually, it feels simple: try a candidate substring, repeat it enough times, and compare with the original string.
The issue is performance. If you try many substring lengths and do repeated concatenations or comparisons, the approach can become slow for long strings. Interviewers may accept it for small constraints, but most expect a more elegant solution that shows stronger string intuition.
The key insight is that you don’t need to rebuild the string repeatedly. Instead, you can detect repetition by analyzing the structure of the string.
Want to explore more coding problem solutions? Check out the Longest String Chain and Minimum Add to Make Parentheses Valid coding problem solutions.
How to solve repeated substring pattern efficiently
There are two widely recognized strategies that interviewers expect you to know conceptually. Both avoid heavy repeated construction and rely on deeper string properties.
Solution approach 1: Use divisors of the string length
If a string is made of repeated substrings, then the substring length must evenly divide the full string length.
That means the valid repeating block lengths are the divisors of n, where n is the string length, excluding n itself. For each candidate length k, the string can only be formed by repetition if every character matches the expected repeating position.
In practice, you verify repetition by checking whether the character at index i matches the character at index i mod k for all positions.
This approach is efficient because you only test plausible lengths, each test is linear in string length, and you stop early when a mismatch is found.
Solution approach 2: The “double string” trick (most elegant)
This is the solution that often gets an interviewer’s attention because it demonstrates strong pattern reasoning.
Here’s the logic: if a string s is made by repeating a substring, then s will appear inside (s + s), but not at the very beginning and not at the very end.
Why does this work? When you concatenate the string with itself, you create overlapping windows where repeated patterns naturally reappear. A truly repetitive string will show up somewhere in the middle of that doubled string.
Conceptually, the check becomes: build a doubled version of the string, then look for the original string inside it after excluding boundary positions.
This avoids testing every substring length directly and relies on a mathematical property of periodic strings.
Common edge cases to watch for
Even without code, it’s worth knowing what can trip people up.
Very short strings are one example. A string of length 1 cannot be formed by repeating a smaller substring.
Strings with all identical characters are another case. These are often valid repetitions, because a single character repeated multiple times still qualifies.
Then there are strings where only part repeats, such as "abcab". These are not valid, because the repeated substring must build the entire string exactly.
Interviewers love to ask about these cases because they reveal whether you truly understand the rule: the repeated substring must reconstruct the whole string with no leftovers.
Top comments (0)