Minimum Time to Revert Word to Initial State I

Minimum Time to Revert Word to Initial State I - 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 = "abacaba", k = 3

› Output: 2

💡 Note: At t=1: remove "aba", remaining = "caba". "caba" is not a prefix of "abacaba". At t=2: remove "abacab", remaining = "a". "a" is a prefix of "abacaba". Return 2.

Example 2 — Immediate Match

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

› Output: 1

💡 Note: At t=1: remove "ab", remaining = "cabc". Need to check if we can form "abcabc" by adding characters. Since "cabc" doesn't match prefix, we continue checking until we find a match.

Example 3 — Complete Removal

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

› Output: 3

💡 Note: At t=1: remove "a", remaining = "bc". At t=2: remove "ab", remaining = "c". At t=3: remove "abc", remaining = "". Empty string can always be reconstructed to original.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Original word and removal count k

Process

Remove k characters, check if suffix can form original

Output

Minimum time when word can revert

Key Takeaway

🎯 Key Insight: The word reverts when its remaining suffix matches a prefix of the original word

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that the word can revert to its initial state when the remaining suffix after removing characters forms a valid prefix of the original word. The optimal approach checks each possible time step and verifies if the suffix matches the original prefix. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ String Matching Optimization	O(n²)	O(1)	Use efficient string matching to find the minimum reversion time
Simulation Approach	O(n²)	O(1)	Simulate the process by checking each possible time step

String Matching Optimization — Algorithm Steps

Calculate maximum possible time steps
For each time t, extract suffix after removing t*k characters
Check if this suffix is a prefix of original word
Return first valid time

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract Suffix

Get remaining characters after removing t*k

Prefix Check

Check if suffix matches original word's prefix

First Match

Return the first time where match occurs

Code -

solution.c — C

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

int solution(char* word, int k) {
    int n = strlen(word);
    
    for (int t = 1; t <= (n + k - 1) / k; t++) {
        int charsToRemove = t * k;
        if (charsToRemove >= n) {
            return t;
        }
        
        char* remaining = word + charsToRemove;
        int remainingLen = strlen(remaining);
        // Check if remaining suffix can be the start of original word
        if (strncmp(word, remaining, remainingLen) == 0) {
            return t;
        }
    }
    
    return (n + k - 1) / k;
}

int main() {
    char word[1001];
    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 O(n/k) time steps, we perform O(n) string prefix matching

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

12.0K Views

Medium Frequency

~15 min Avg. Time

245 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

String Matching Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler