3031. Minimum Time to Revert Word to Initial State II LeetCode Solution
In this guide, you will get 3031. Minimum Time to Revert Word to Initial State II LeetCode Solution with the best time and space complexity. The solution to Minimum Time to Revert Word to Initial State II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 k characters of word.
Add any k characters to the end of word.
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 = 3
Output: 2
Explanation: At the 1st second, we remove characters “aba” from the prefix of word, and add characters “bac” to the end of word. Thus, word becomes equal to “cababac”.
At the 2nd second, we remove characters “cab” from the prefix of word, and add “aba” to the end of word. Thus, word becomes equal to “abacaba” and reverts to its initial state.
It can be shown that 2 seconds is the minimum time greater than zero required for word to revert to its initial state.
Input: word = “abacaba”, k = 4
Output: 1
Explanation: At the 1st second, we remove characters “abac” from the prefix of word, and add characters “caba” to the end of word. Thus, word becomes equal to “abacaba” and reverts to its initial state.
It can be shown that 1 second is the minimum time greater than zero required for word to revert to its initial state.
Example 3:
Input: word = “abcbabcd”, k = 2
Output: 4
Explanation: At every second, we will remove the first 2 characters of word, and add the same characters to the end of word.
After 4 seconds, word becomes equal to “abcbabcd” and reverts to its initial state.
It can be shown that 4 seconds is the minimum time greater than zero required for word to revert to its initial state.
Constraints:
1 <= word.length <= 106
1 <= k <= word.length
word consists only of lowercase English letters.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
3031. Minimum Time to Revert Word to Initial State II LeetCode Solution in C++
class Solution {
public:
// Same as 3029. Minimum Time to Revert Word to Initial State I
int minimumTimeToInitialState(string word, int k) {
const int n = word.length();
const int maxOps = (n - 1) / k + 1;
const vector<int> z = zFunction(word);
for (int ans = 1; ans < maxOps; ++ans)
if (z[ans * k] >= n - ans * k)
return ans;
return maxOps;
}
// Returns the z array, where z[i] is the length of the longest prefix of
// s[i..n) which is also a prefix of s.
//
// https://cp-algorithms.com/string/z-function.html#implementation
vector<int> zFunction(const string& s) {
const int n = s.length();
vector<int> z(n);
int l = 0;
int r = 0;
for (int i = 1; i < n; ++i) {
if (i < r)
z[i] = min(r - i, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]])
++z[i];
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return z;
}
}; /* code provided by PROGIEZ */
3031. Minimum Time to Revert Word to Initial State II LeetCode Solution in Java
class Solution {
// Same as 3029. Minimum Time to Revert Word to Initial State I
public int minimumTimeToInitialState(String word, int k) {
final int n = word.length();
final int maxOps = (n - 1) / k + 1;
final int[] z = zFunction(word);
for (int ans = 1; ans < maxOps; ++ans)
if (z[ans * k] >= n - ans * k)
return ans;
return maxOps;
}
// Returns the z array, where z[i] is the length of the longest prefix of
// s[i..n) which is also a prefix of s.
//
// https://cp-algorithms.com/string/z-function.html#implementation
private int[] zFunction(final String s) {
final int n = s.length();
int[] z = new int[n];
int l = 0;
int r = 0;
for (int i = 1; i < n; ++i) {
if (i < r)
z[i] = Math.min(r - i, z[i - l]);
while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i]))
++z[i];
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return z;
}
} // code provided by PROGIEZ
3031. Minimum Time to Revert Word to Initial State II LeetCode Solution in Python
class Solution:
# Same as 3029. Minimum Time to Revert Word to Initial State I
def minimumTimeToInitialState(self, word: str, k: int) -> int:
n = len(word)
maxOps = (n - 1) // k + 1
z = self._zFunction(word)
for ans in range(1, maxOps):
if z[ans * k] >= n - ans * k:
return ans
return maxOps
def _zFunction(self, s: str) -> list[int]:
"""
Returns the z array, where z[i] is the length of the longest prefix of
s[i..n) which is also a prefix of s.
https://cp-algorithms.com/string/z-function.html#implementation
"""
n = len(s)
z = [0] * n
l = 0
r = 0
for i in range(1, n):
if i < r:
z[i] = min(r - i, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] > r:
l = i
r = i + z[i]
return z # code by PROGIEZ
