Repeated Substring Pattern
The key idea
If
s is a repeat of some block, then doubling it and stripping one character off each end leaves a copy of s still inside. So s is periodic exactly when s appears in (s+s) with the very first and very last characters removed.Problem
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
Return true if it can be built this way, and false otherwise.
Constraints
- 1 <= s.length <= 10^4
sconsists of lowercase English letters.
Examples
Input: s = "abab"
Output: true
Input: s = "aba"
Output: false
Input: s = "abcabcabcabc"
Output: true
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization