Minimum Time to Revert Word to Initial State I — Solution
Minimum Time to Revert Word to Initial State I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Time to Revert Word to Initial State I is a medium coding problem on strings, rolling hash and string matching, asked in Google interviews.
- Difficulty: Medium
- Topics: Strings, Rolling Hash, String Matching
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string word and an integer k.
Every second you must do both of the following:
- remove the first
kcharacters ofword, and - append any
kcharacters of your choice to the end ofword.
The characters you append do not have to be the ones you removed. Return the minimum time greater than zero after which word can be back in its initial state.
Example 1
Input: word = "abacaba", k = 3
Output: 2
Explanation: After 1 second the word could be "cababac" (it must start with "caba", which is not a prefix of "abacaba"). After 2 seconds the kept part is just "a", which is a prefix, so append "bacaba" to restore it.
Example 2
Input: word = "abacaba", k = 4
Output: 1
Explanation: Removing "abac" keeps "aba", a prefix of the word; appending "caba" restores it at once.
Example 3
Input: word = "abcbabcd", k = 2
Output: 4
Explanation: No kept suffix is a prefix until all 8 characters have been replaced after 4 seconds.
Constraints
1 <= word.length <= 501 <= k <= word.lengthword consists only of lowercase English letters
Hints for Minimum Time to Revert Word to Initial State I
Hint 1
After
tseconds the firstt * kcharacters are gone; what remains of the original word is its suffix starting at indext * k, followed by characters you chose freely.Hint 2
You can rebuild the original exactly when that surviving suffix equals the word's prefix of the same length — the free characters fill in the rest.
Hint 3
Try
t = 1, 2, …in order. Oncet * k >= nnothing original survives and the answer is thatt.
How to solve Minimum Time to Revert Word to Initial State I
Only the original characters that have not yet been removed constrain the result. After t seconds those are word[t*k..], sitting at the front; the word can be restored exactly when that suffix is also a prefix of word.
Approach
- For
t = 1, 2, 3, …: leti = t * k. - If
i >= n, every original character is gone — returnt. - If
word[i..]equalsword[0 .. n - i), returnt.
Why it works
The appended characters are arbitrary, so after t seconds the word is word[i..] followed by any i characters. That equals the original iff word[i..] matches the original's first n - i characters (then append the original's last i). Checking t in increasing order returns the minimum.
Complexity
- Time —
O(n^2 / k) - Space —
O(1) beyond the compared substrings
Pitfalls
- The answer is never 0 — at least one second must pass.
- When
t * kpassesnthe answer isceil(n / k), notn / k.
Reference solution
Python
def minimumTimeToInitialState(word: str, k: int) -> int:
n = len(word)
t = 1
while t * k < n:
if word.startswith(word[t * k:]):
return t
t += 1
return tJava
public static int minimumTimeToInitialState(String word, int k) {
int n = word.length(), t = 1;
while (t * k < n) {
if (word.startsWith(word.substring(t * k))) return t;
t++;
}
return t;
}C++
int minimumTimeToInitialState(string word, int k) {
int n = word.size(), t = 1;
while (t * k < n) {
int i = t * k;
if (word.compare(i, n - i, word, 0, n - i) == 0) return t;
t++;
}
return t;
}JavaScript
var minimumTimeToInitialState = function(word, k) {
var n = word.length, t = 1;
while (t * k < n) {
var i = t * k, ok = true;
for (var j = 0; i + j < n; j++) {
if (word[i + j] !== word[j]) { ok = false; break; }
}
if (ok) return t;
t++;
}
return t;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings