Minimum Time to Revert Word to Initial State I

Medium
1763.

Minimum Time to Revert Word to Initial State I

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.

You are given a string word and an integer k.

Every second you must do both of the following:

  • remove the first k characters of word, and
  • append any k characters of your choice to the end of word.

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 <= 50
  • 1 <= k <= word.length
  • word consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @param {number} k
 * @return {number}
 */
var minimumTimeToInitialState = function(word, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 k characters of word, and
  • append any k characters of your choice to the end of word.

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 <= 50
  • 1 <= k <= word.length
  • word consists only of lowercase English letters

Hints for Minimum Time to Revert Word to Initial State I

  1. Hint 1

    After t seconds the first t * k characters are gone; what remains of the original word is its suffix starting at index t * k, followed by characters you chose freely.

  2. 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.

  3. Hint 3

    Try t = 1, 2, … in order. Once t * k >= n nothing original survives and the answer is that t.

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

  1. For t = 1, 2, 3, …: let i = t * k.
  2. If i >= n, every original character is gone — return t.
  3. If word[i..] equals word[0 .. n - i), return t.

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 * k passes n the answer is ceil(n / k), not n / 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 t

Java

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