Repeated Substring Pattern
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.
The repeating substring must tile the string evenly, so 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. The candidate length can also be at most n/2, since the string must hold at least two copies.
This divisibility constraint limits the search. We do not need to try every possible substring, only 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
Try every possible substring length that could work, build the repeated string from it, and check whether it matches the original.
Since the repeating unit must tile the entire string, its length has to divide n evenly, and the string needs at least two copies, so the maximum candidate length is n/2. For each valid candidate length len, take the first len characters as the candidate substring, repeat it n/len times, and compare with s.
Algorithm
- Get the length
nof the string. - For each candidate length
lenfrom 1 ton/2: - If
n % len != 0, skip this length (it cannot tile the string evenly). - Build the candidate by repeating
s[0..len-1]exactlyn/lentimes. - 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!
Code
- 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 builds a fresh string for each candidate length. The next approach detects repetition without constructing any candidate strings.
Approach 2: String Concatenation Trick
Intuition
If s is made of a repeating pattern, then concatenating s with itself to form s + s produces a doubled string in which the original s appears somewhere in the middle, not only at the start and end positions.
Take s = "abcabc". The repeating unit is "abc". Forming s + s = "abcabcabcabc" gives four copies of "abc" in a row. The original s appears starting at position 0 and at position 6 (the two endpoints), but it also appears starting at position 3, since positions 3 through 8 spell "abcabc".
If s has no repeating pattern, then s appears in s + s only at positions 0 and n, and nowhere in between.
The algorithm follows from this: form s + s, remove the first and last characters to destroy the two endpoint matches, and check whether s still appears in the result. If it does, the string has a repeating pattern.
If s is built by repeating a substring p exactly k times (with k >= 2), then s + s is p repeated 2k times. The original s can start at any multiple of |p| within this doubled string: positions 0, |p|, 2|p|, and so on up to position n. The endpoint starts are 0 and n; removing the first and last characters destroys only those two, so at least one interior start (for example |p|) survives, and the search succeeds.
If s has no repeating period shorter than n, then a copy of s aligns inside s + s only at offsets 0 and n. Removing both endpoints leaves no place for s to match, so the search fails.
Algorithm
- Concatenate
swith itself to formdoubled = s + s. - Remove the first character and last character from
doubledto gettrimmed. - If
sis found as a substring withintrimmed, return true. - Otherwise, return false.
Example Walkthrough
Code
- Time Complexity: O(n). String concatenation is O(n), and the substring search runs in O(n) when the standard library uses a linear matcher. Some standard libraries use a naive O(n*m) search, which would make this O(n^2) in the worst case, so the linear bound depends on the implementation.
- Space Complexity: O(n). We create the doubled string of length 2n and the trimmed string of length 2n - 2.
This approach depends on the language's built-in substring search. The next approach detects the repeating period directly from the structure of the string, with a guaranteed linear bound.
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.
If a string of length n has a repeating pattern of length k, then the failure function value at the last position is n - k, that is, fail[n-1] = n - k. 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).
The failure function at position i gives the length of the longest proper prefix of s[0..i] that is also a suffix. For "abcabcabc", fail[8] = 6 means the first 6 characters ("abcabc") match the last 6 characters ("abcabc"). This overlap between prefix and suffix is what a periodic string produces.
The non-overlapping part has length n - fail[n-1], the fundamental repeating unit. If this length divides n evenly, the entire string is that unit repeated. The condition fail[n-1] > 0 ensures there is some overlap at all (a string with no internal repetition has 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 > 0andn % patternLen == 0, return true. - Otherwise, return false.
Example Walkthrough
Code
- 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.