Understanding the Problem

We need to determine if the entire string s is made up of some shorter substring repeated two or more times. So if s = "abab", the answer is true because "ab" repeated twice gives us "abab". But if s = "aba", there is no substring we can repeat to get the original string.

A few things to notice upfront. The repeating substring must divide the string evenly, meaning its length must be a divisor of the total string length. If the string has length 6, the candidate substring could have length 1, 2, or 3, but not 4 or 5. Also, the candidate substring length can be at most n/2 because we need at least two copies.

This divisibility constraint is what gives us a foothold. We do not need to try every possible substring, just the ones whose lengths divide n evenly.

Key Constraints:

1 <= s.length <= 10^4 — With n up to 10,000, O(n^2) is feasible (100 million operations at worst). O(n * sqrt(n)) and O(n) are comfortable.
s consists of lowercase English letters — Standard character set, no special encoding concerns.

Approach 1: Brute Force (Check All Divisor Lengths)

Intuition

The most natural approach: try every possible substring length that could work, build the repeated string, and see if it matches the original.

Since the repeating unit must tile the entire string, its length has to divide n evenly. And we need at least two copies, so the maximum candidate length is n/2. For each valid candidate length len, we take the first len characters as our candidate substring, repeat it n/len times, and compare with s.

This is straightforward and easy to code correctly under interview pressure. For n up to 10^4, it runs fast enough.

Algorithm

Get the length n of the string.
For each candidate length len from 1 to n/2:

a. If n % len != 0, skip this length (it cannot tile the string evenly).

b. Build the candidate by repeating s[0..len-1] exactly n/len times.

c. If the built string equals s, return true.

If no candidate length worked, return false.

Example Walkthrough

Input:

Try len=1: candidate "a", repeat 4 times = "aaaa" != "abab". Skip.

Try len=2: candidate "ab", repeat 2 times = "abab" == "abab". Match!

true

result

Code

Complexity Analysis

Time Complexity: O(n d(n)). We check each divisor of n, and for each one we build and compare a string of length n. In practice this is roughly O(n sqrt(n)), but can degrade to O(n^2) in the worst case.
Space Complexity: O(n). We build a string of length n for comparison.

This approach works but builds entirely new strings for each candidate length. What if we could detect repetition without constructing any new strings at all?

Approach 2: String Concatenation Trick

Intuition

Here is the elegant insight: if s is made of a repeating pattern, then when you concatenate s with itself to get s + s, the original s will appear somewhere in the middle of this doubled string (not just at the start and end positions).

Why? Say s = "abcabc". The repeating unit is "abc". When we form s + s = "abcabcabcabc", we get four copies of "abc" in a row. The original s appears starting at position 0 (trivially) and at position 6 (trivially), but it also appears starting at position 3 because positions 3-8 give us "abcabc".

Conversely, if s has no repeating pattern, then s only appears in s + s at positions 0 and n. Nowhere else.

So the algorithm is: form s + s, chop off the first and last characters (to eliminate the trivial matches at positions 0 and n), and check if s still appears in the result. If it does, the string has a repeating pattern.

Why does this work?

If s is built by repeating a substring p exactly k times (where k >= 2), then s + s is p repeated 2k times. The original s (which is p repeated k times) can start at any multiple of |p| within this doubled string. The trivial starts are at positions 0 and n, but there are also valid starts at positions |p|, 2|p|, etc. Removing the first and last characters destroys the trivial matches at positions 0 and n, but at least one of the intermediate matches survives.

If s has no repeating pattern, then s only appears at positions 0 and n in s + s. Removing those endpoints means s will not be found.

Algorithm

Concatenate s with itself to form doubled = s + s.
Remove the first character and last character from doubled to get trimmed.
If s is found as a substring within trimmed, return true.
Otherwise, return false.

Example Walkthrough

1Start: s = "abab", form s + s = "abababab"

s (copy 1)

s (copy 2)

1/5

Code

Complexity Analysis

Time Complexity: O(n). String concatenation is O(n). The substring search uses optimized algorithms under the hood that run in O(n). So the total is O(n).
Space Complexity: O(n). We create the doubled string of length 2n and the trimmed string of length 2n - 2.

The concatenation trick is elegant, but it relies on the language's built-in substring search. Can we detect the repeating pattern directly using the structure of the string itself?

Approach 3: KMP-Based (Failure Function)

Intuition

The KMP (Knuth-Morris-Pratt) algorithm's failure function reveals the internal repetitive structure of a string. The failure function for each position i stores the length of the longest proper prefix of s[0..i] that is also a suffix.

Here is the key insight: if a string of length n has a repeating pattern of length k, then the failure function value at the last position will be n - k. In other words, fail[n-1] = n - k. This means the string has a suffix of length n - k that matches a prefix of length n - k, and the remaining part (length k) is the repeating unit.

For this to represent a valid repeating pattern, k must divide n evenly. So the condition is: fail[n-1] > 0 (there is some prefix-suffix match) and n % (n - fail[n-1]) == 0 (the repeating unit length divides the string length).

Why does this work?

The failure function at position i tells us the longest proper prefix of s[0..i] that is also a suffix. For a string like "abcabcabc", fail[8] = 6 means the first 6 characters ("abcabc") match the last 6 characters ("abcabc"). The overlap between prefix and suffix is what creates the repeating structure.

The non-overlapping part has length n - fail[n-1], which is the fundamental repeating unit. If this length divides n evenly, then the entire string is just this unit repeated. The condition fail[n-1] > 0 ensures there is actually some overlap (a string with no internal repetition would have fail[n-1] = 0).

Algorithm

Build the KMP failure function array for the string s.
Let failLast = fail[n-1], the failure function value at the last index.
Compute the candidate pattern length: patternLen = n - failLast.
If failLast > 0 and n % patternLen == 0, return true.
Otherwise, return false.

Example Walkthrough

1Initialize: build failure function for s = "abcabcabc"

i=0

1/6

1Initialize failure function array with zeros

1/6

Code

Complexity Analysis

Time Complexity: O(n). Building the KMP failure function takes O(n) time. The final check is O(1). Even though the while loop has an inner fallback step, the total number of iterations is bounded by n.
Space Complexity: O(n). The failure function array requires O(n) space.

Repeated Substring Pattern

Understanding the Problem

Key Constraints:

Approach 1: Brute Force (Check All Divisor Lengths)

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: String Concatenation Trick

Intuition

Algorithm

Example Walkthrough

Code

Approach 3: KMP-Based (Failure Function)

Intuition

Algorithm

Example Walkthrough

Code

Get Premium