Minimum Time to Revert Word to Initial State II
You are given a 0-indexed string word and an integer k.
At every second, you must perform the following operations:
- Remove the first
kcharacters ofword. - Add any
kcharacters to the end ofword.
Note that you do not necessarily need to add the same characters that you removed. However, you must perform both operations at every second.
Return the minimum time greater than zero required for word to revert to its initial state.
Example 1
Input
word = "abacaba", k = 3Output
2At the 1st second, removing "aba" and adding "bac" makes
word equal to "cababac", and at the 2nd second it can revert to "abacaba", which is the minimum time greater than zero.Example 2
Input
word = "abacaba", k = 4Output
1At the 1st second, removing "abac" and adding "caba" makes
word equal to "abacaba", so the minimum time greater than zero is 1 second.Constraints
- 1 <= word.length <= 10^6
- 1 <= k <= word.length
- word consists only of lowercase English letters.