将单词恢复初始状态所需的最短时间 II

难度: Hard

给你一个下标从 0 开始的字符串 word 和一个整数 k 。

在每一秒，你必须执行以下操作：

移除 word 的前 k 个字符。
在 word 的末尾添加 k 个任意字符。

注意添加的字符不必和移除的字符相同。但是，必须在每一秒钟都执行两种操作。

返回将 word 恢复到其初始状态所需的最短时间（该时间必须大于零）。

示例 1：

输入：word = "abacaba", k = 3
输出：2
解释：
第 1 秒，移除 word 的前缀 "aba"，并在末尾添加 "bac" 。因此，word 变为 "cababac"。
第 2 秒，移除 word 的前缀 "cab"，并在末尾添加 "aba" 。因此，word 变为 "abacaba" 并恢复到始状态。
可以证明，2 秒是 word 恢复到其初始状态所需的最短时间。

示例 2：

输入：word = "abacaba", k = 4
输出：1
解释：
第 1 秒，移除 word 的前缀 "abac"，并在末尾添加 "caba" 。因此，word 变为 "abacaba" 并恢复到初始状态。
可以证明，1 秒是 word 恢复到其初始状态所需的最短时间。

示例 3：

输入：word = "abcbabcd", k = 2
输出：4
解释：
每一秒，我们都移除 word 的前 2 个字符，并在 word 末尾添加相同的字符。
4 秒后，word 变为 "abcbabcd" 并恢复到初始状态。
可以证明，4 秒是 word 恢复到其初始状态所需的最短时间。

提示：

1 <= word.length <= 10⁶
1 <= k <= word.length
word仅由小写英文字母组成。

Submission

运行时间: 81 ms

内存: 16.8 MB

class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        n = len(word)
        a, b, i = 1, ceil(n / k), k
        while a < b:
            c = a + b >> 1
            t = n - c * k
            i1 = word.find(word[:t], i)
            if i1 < 0 or word.find(word[-t:]) > n - a * k - t:
                a = c + 1
                continue
            i = i1
            if i % k == 0 and (i == n - t or word.find(word[i + t:], t) == t):
                return i // k
            i = ceil(i / k) * k
            a, b = max(a, i // k), c
        t = n - a * k
        if t <= 0:
            return a
        a, b = word[:t], word[-t:]
        if a == b:
            return (n - len(a)) // k
        a, b = deque(a), deque(b)
        while len(a) >= k:
            for _ in range(k):
                a.pop()
                b.popleft()
            if a == b:
                return (n - len(a)) // k
        return ceil(n / k)

Explain

此题解采用二分查找的方法来确定最短时间。首先，初始化时间的可能范围为 [1, ceil(n/k)]，其中 n 是字符串长度。在每次迭代中，计算中间值 c 作为当前秒数尝试，计算剩余长度 t = n - c * k。接着，尝试在字符串中找到前缀 word[:t] 和后缀 word[-t:] 的匹配位置。如果找到合适的匹配，尝试缩小时间范围；如果没有找到，增加时间尝试。最终确定出最小时间。特别注意边界条件的处理，例如 t <= 0 的情况，以及在字符串中寻找匹配的过程中的边界检查。

时间复杂度: O(n log(n/k))

空间复杂度: O(n)

class Solution:
    def minimumTimeToInitialState(self, word: str, k: int) -> int:
        n = len(word)
        a, b, i = 1, ceil(n / k), k
        while a < b:
            c = (a + b) >> 1
            t = n - c * k
            i1 = word.find(word[:t], i)
            if i1 < 0 or word.find(word[-t:]) > n - a * k - t:
                a = c + 1
                continue
            i = i1
            if i % k == 0 and (i == n - t or word.find(word[i + t:], t) == t):
                return i // k
            i = ceil(i / k) * k
            a, b = max(a, i // k), c
        t = n - a * k
        if t <= 0:
            return a
        a, b = word[:t], word[-t:]
        if a == b:
            return (n - len(a)) // k
        a, b = deque(a), deque(b)
        while len(a) >= k:
            for _ in range(k):
                a.pop()
                b.popleft()
            if a == b:
                return (n - len(a)) // k
        return ceil(n / k)

Explore

二分查找的思路基于将问题的解空间分割成两部分，一部分保证不包含解，另一部分可能包含解，然后逐渐缩小可能包含解的空间。在本题中，解空间是可能的最短时间，范围从1到ceil(n/k)。二分查找适用于这个问题因为时间越长，恢复初始状态所需满足的条件就越容易达成，所以存在一个时间阈值，小于这个阈值的时间无法恢复到初始状态，而大于等于这个阈值的时间可以。这样，时间和是否能恢复状态之间存在一个单调关系，适合使用二分查找来快速定位到这个阈值，找到最短的时间。

在每次二分查找迭代中，通过设定一个中间值c来尝试是否可以在c秒内恢复到初始状态。这通过计算剩余长度t = n - c * k，并检查字符串中是否存在与word[:t]和word[-t:]匹配的位置来决定。如果在当前时间c内可以找到这样的匹配位置，则尝试减小时间尝试，即调整上界b = c；如果找不到，则增加时间尝试，调整下界a = c + 1。这样不断调整搜索范围的上下界，直到找到最小的满足条件的c。

边界条件`t <= 0`表示试图在c秒内恢复单词到初始状态时，剩余的未处理长度t变成了非正数，即剩余的字符数量不足以进行进一步的比较。这种情况通常发生在c值过大时，说明试图在这么短的时间内完成任务是不可能的。在这种情况下，应该处理为直接返回当前的时间尝试值a，因为此时已经没有必要再寻找更大的时间值，而是应该确认在此时间内任务已经无法完成，因此返回当前最小尝试时间。