Minimum Time to Revert Word to Initial State I

Minimum Time to Revert Word to Initial State I

What is this problem about?

The Minimum Time to Revert Word to Initial State I problem gives you a string word and an integer k. In each second, you remove the first k characters and append any k characters to the end. Find the minimum number of operations needed to return the word to its initial state (any appended characters are chosen optimally). This Minimum Time to Revert Word to Initial State I coding problem uses string matching to determine when a suffix of the word matches its prefix.

Why is this asked in interviews?

Sprinklr asks this to test string matching pattern knowledge, specifically the Z-function or KMP failure function. The key insight: after t operations, word[t*k:] is the suffix that must be a prefix of the original word (since you can freely choose appended characters). The string matching, hash function, rolling hash, and string interview pattern is directly applied.

Algorithmic pattern used

Z-function or KMP prefix function. After t operations, the remaining original suffix is word[t*k:]. For word[t*k:] to be repairable to the original, word[t*k:] must be a prefix of word. Use the Z-function: Z[i] = length of the longest prefix of word that matches the substring starting at i. Check if Z[t*k] >= len(word) - t*k for each t = 1, 2, ... Return the smallest such t.

Example explanation

word = "abacaba", k = 2.

• t=1: check if word[2:] = "acaba" is a prefix of "abacaba". Z[2] = 1 (only 'a' matches). 1 < 5. No.
• t=2: check word[4:] = "aba". Z[4] = 3. 3 ≥ 3. Yes! Minimum t = 2.

Common mistakes candidates make

• Not recognizing the Z-function / KMP connection.
• Checking prefix matching with naive string comparison (O(n²)).
• Forgetting that appended characters are chosen freely — only the remaining suffix needs to be a prefix.
• Not checking when t*k ≥ len(word) (after enough operations, always solvable in 1 more step).

Interview preparation tip

String reversion/transformation problems that ask "when does a suffix become a prefix" are solved with the Z-function or KMP. Internalize the Z-function template: Z[i] gives the length of the longest common prefix between word and word[i:]. If Z[i] + i >= len(word), then word[i:] is a prefix of word. Practicing Z-function and KMP on a variety of string matching problems is essential for string-heavy interviews at companies like Sprinklr, Google, and Meta.