66. Built From a Block
A sticker printer produces a strip of lowercase letters s, and a quality inspector wants to know whether the strip is only one short pattern copied over and over. The strip is built from a block if some shorter non-empty string, repeated two or more times in a row, gives exactly s.
Return true if s is built from a block, and false otherwise. A strip of length 1 can never be built from a shorter block, and a strip is never counted as a block of itself repeated once.
Example 1
- Input:
- s = "qrsqrsqrs"
- Output:
- true
- Explanation:
The block qrs repeated three times gives the strip.
Example 2
- Input:
- s = "qrsqr"
- Output:
- false
- Explanation:
No shorter block repeated whole times gives qrsqr, so the answer is false.
Constraints
1 ≤ s.length ≤ 105
s contains only lowercase English letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n * d(n))
- Space
- O(1)