369. Repeated Substring Pattern
You are given a string s of lowercase English letters.
Decide whether the whole string can be produced by taking some substring of it and writing that substring back-to-back two or more times. In other words: is there a block shorter than s whose repetition rebuilds s exactly?
Return true if such a block exists and false otherwise.
Example 1:
Input: s = "abab"
Output: true
Explanation: The block "ab" written twice rebuilds the string.
Example 2:
Input: s = "aba"
Output: false
Explanation: No block shorter than the string repeats cleanly: "a" three times gives "aaa", and a block of length 2 cannot tile a string of length 3.
Example 3:
Input: s = "abcabcabc"
Output: true
Explanation: The block "abc" written three times rebuilds the string.
Constraints:
- 1 ≤ s.length ≤ 10⁴
- s consists of lowercase English letters only
Hints:
If a block of length L tiles the string, L must divide len(s) evenly, and L is at most len(s) / 2. That leaves only the divisors of the length to try.
A slick shortcut: write the string twice in a row, chop off the first and last character, and ask whether the original still appears inside. It does exactly when the string is periodic.
For a guaranteed linear bound, compute the KMP failure function. If f is the length of the longest proper border of s, the smallest period is n − f, and the answer is yes exactly when that period divides n and f > 0.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "abab"
Expected output: true