Minimum Time to Revert Word to Initial State II

Minimum Time to Revert Word to Initial State II - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: word = "abcab", k = 2

› Output: 3

💡 Note: At t=1: remove "ab" → "cab", can't restore. At t=2: remove "abca" → "b", can't restore. At t=3: remove all → "", can add "abcab" to restore original.

Example 2 — Early Return

$ Input: word = "abab", k = 2

› Output: 2

💡 Note: At t=1: remove "ab" → "ab", can add "ab" to get "abab". But this doesn't work. At t=2: remove "abab" → "", can restore by adding "abab".

Example 3 — Single Character

$ Input: word = "a", k = 1

› Output: 1

💡 Note: At t=1: remove "a" → "", can add "a" to restore original word.

Constraints

1 ≤ word.length ≤ 10⁶
1 ≤ k ≤ word.length
word consists only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Original word and removal size k

Process

Remove k chars each second, check if restorable

Output

Minimum time to restore original word

Key Takeaway

🎯 Key Insight: Find the smallest time where the remaining suffix can be extended to match the original word

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that we need to find the minimum time t where the remaining suffix after removing k*t characters can be extended to match the original word. The brute force approach checks each time step with string matching in O(n²) time. The optimized approach uses KMP preprocessing for more efficient pattern matching. Best approach depends on string patterns: Time O(n²), Space O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force String Matching	O(n²)	O(1)	Check each time step by simulating the process and testing if restoration is possible
String Matching with KMP	O(n²)	O(n)	Use efficient string matching to check if suffix can be extended to original word

Brute Force String Matching — Algorithm Steps

Iterate through time steps t = 1, 2, 3, ...
For each t, get suffix starting at position k*t
Check if this suffix can be extended to match original word

Visualization

Tap to expand

Step-by-Step Walkthrough

Remove k chars

Remove first k characters at each step

Check suffix

See if remaining suffix can form original

Found match

Return the time when restoration is possible

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* word, int k) {
    int n = strlen(word);
    
    for (int t = 1; t <= (n + k - 1) / k; t++) {
        int startPos = (k * t) % n;
        if (startPos == 0) {
            return t;
        }
        
        // Check if suffix can be extended to match original
        char* suffix = word + startPos;
        if (strncmp(word, suffix, strlen(suffix)) == 0) {
            // Check if the remaining part matches
            int remainingLen = n - strlen(suffix);
            if (remainingLen == 0 || strncmp(word, word + strlen(suffix), remainingLen) == 0) {
                return t;
            }
        }
    }
    
    return (n + k - 1) / k;
}

int main() {
    char word[100001];
    int k;
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(word, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n/k possible time steps, we perform O(n) string matching

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force String Matching — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler