Repeated Substring Pattern (LeetCode 459)

The problem

Given a string s, decide whether it can be built by writing some shorter substring two or more times in a row.

Input:  s = "abab"
Output: True

"abab" is "ab" written twice. By contrast "aba" gives False: no shorter block repeats to make it.

How to think about it

Start with brute force. Try every block length L that divides n, and check whether s[:L] * (n // L) == s. Each check is O(n), and there are as many candidates as divisors of n, so this is fine in practice (roughly O(n·d(n))). But there’s a neater idea.

The key insight: a repeated string reappears inside its own double. Write t = s + s. If s is a block B repeated, say s = BBB, then t = BBBBBB and s also appears starting at position len(B), which is strictly inside t. If s has no such period, the only places s appears in t are position 0 and position n. So chop the first and last characters off t to kill those two trivial matches, and ask whether s is still in there.

Why chopping works. Removing t[0] kills the match at 0, and removing t[-1] kills the match at n. Any match that remains starts at some 0 < p < n, which means rotating s by p gives s again, and that happens exactly when s has period p dividing n.

Which pattern is this? String periodicity. The KMP view is the same fact: with the prefix function lps, s is repeated exactly when lps[-1] > 0 and n - lps[-1] divides n. The tell is “is this string made of a repeated block?”

Approach

1. Build s + s.
2. Drop its first and last characters: (s + s)[1:-1].
3. Return whether s is a substring of that.

Solution

def repeatedSubstringPattern(s):
    # s reappears strictly inside its double iff it has a repeating block
    return s in (s + s)[1:-1]
# repeatedSubstringPattern("abab") -> True ;  repeatedSubstringPattern("aba") -> False

Dry run

Running the code on both examples:

For "abab", s is found at index 1 of the trimmed string, which is position 2 of s + s: a shift of 2, the length of the block "ab".

Complexity

• Time: O(n) with a linear substring search (KMP or similar). CPython’s in is fast in practice, though its worst case is not guaranteed linear.
• Space: O(n). For the doubled string.

Edge cases and pitfalls

• Single character ("a") is False: the block must be repeated at least twice, and the trimmed string is empty.
• All the same character ("aaaa") is True, with block "a".
• Forgetting to trim makes every string match itself at index 0, so everything returns True.
• Trimming only one end still leaves the match at position n (or 0). Trim both.
• Checking only L = n // 2 misses cases like "abcabcabc", where the block length is n / 3.

Related problems

• Find the Index of the First Occurrence in a String (LeetCode 28): the KMP search that makes in linear.
• Longest Happy Prefix (LeetCode 1392): lps[-1], the quantity behind the KMP version of this check.
• Repeated String Match (LeetCode 686): another question about repeating a string.