Scale Engineer

Minimum Time to Revert Word to Initial State I

Med
#2697Time: O(N^2 / K), where N is the length of the word. The loop runs up to `O(N/K)` times. In each iteration, creating and comparing substrings of length up to N takes `O(N)` time.Space: O(N) in Java, where N is the length of the word. This is due to the creation of new substring objects in each iteration. If `regionMatches` is used, the space complexity is O(1).1 company
Patterns
String MatchingRolling HashHash Function
Data structures
String
Companies
Sprinklr

Prompt

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.

 

Example 1:

Input: word = "abacaba", k = 3
Output: 2
Explanation: At the 1st second, we remove characters "aba" from the prefix of word, and add characters "bac" to the end of word. Thus, word becomes equal to "cababac".
At the 2nd second, we remove characters "cab" from the prefix of word, and add "aba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state.
It can be shown that 2 seconds is the minimum time greater than zero required for word to revert to its initial state.

Example 2:

Input: word = "abacaba", k = 4
Output: 1
Explanation: At the 1st second, we remove characters "abac" from the prefix of word, and add characters "caba" to the end of word. Thus, word becomes equal to "abacaba" and reverts to its initial state.
It can be shown that 1 second is the minimum time greater than zero required for word to revert to its initial state.

Example 3:

Input: word = "abcbabcd", k = 2
Output: 4
Explanation: At every second, we will remove the first 2 characters of word, and add the same characters to the end of word.
After 4 seconds, word becomes equal to "abcbabcd" and reverts to its initial state.
It can be shown that 4 seconds is the minimum time greater than zero required for word to revert to its initial state.

 

Constraints:

  • 1 <= word.length <= 50
  • 1 <= k <= word.length
  • word consists only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This is a straightforward approach that iterates through the possible times t=1, 2, ... and for each time, checks if the condition for reverting to the initial state is met. The condition is that a suffix of the original word must match a prefix of the same length.

Algorithm

    1. Get the length of the word, n.
    1. Start a loop for time t from 1. The loop should continue as long as t * k < n.
    1. Inside the loop, calculate the number of characters removed, p = t * k.
    1. Check if the prefix of word of length n-p is equal to the suffix of word starting at index p. This can be done using string slicing and comparison.
    1. If they are equal, it means we can revert the word to its initial state. Return the current time t as it's the minimum.
    1. If the loop completes without finding such a t, it means no period t*k exists for t*k < n. The answer is then the smallest t such that t*k >= n, which is ceil(n/k). Return (n + k - 1) / k.

Walkthrough

The problem can be rephrased as finding the smallest integer t > 0 such that word has a period of p = t * k. A string s of length n has a period p if its prefix of length n-p is equal to its suffix of length n-p (which starts at index p).

We can iterate t starting from 1. For each t, we calculate the potential period p = t * k.

We only need to check for p < n. If p >= n, it means we have conceptually removed at least n characters. In this scenario, we can always reconstruct the original word. The minimum time t for this to happen is ceil(n/k).

For each t where p = t*k < n, we check if word.substring(0, n - p) is equal to word.substring(p).

The first t that satisfies this condition is the minimum time required, so we return it.

If the loop finishes without finding such a t, it means no period t*k exists for t*k < n. The answer is then ceil(n/k).

class Solution {    public int minimumTimeToInitialState(String word, int k) {        int n = word.length();        for (int t = 1; t * k < n; ++t) {            int p = t * k;            // Check if word has period p.            // This is equivalent to checking if the suffix of length n-p            // is equal to the prefix of length n-p.            // The suffix starts at index p.            if (word.substring(p).equals(word.substring(0, n - p))) {                return t;            }        }        // If no such shorter period is found, the answer is the time        // needed to remove at least n characters.        return (n + k - 1) / k;    }}

A small optimization is to use word.regionMatches() to avoid creating new substring objects, which can be more efficient.

// Alternative check inside the loop// if (word.regionMatches(0, word, p, n - p)) {//     return t;// }

Complexity

Time

O(N^2 / K), where N is the length of the word. The loop runs up to `O(N/K)` times. In each iteration, creating and comparing substrings of length up to N takes `O(N)` time.

Space

O(N) in Java, where N is the length of the word. This is due to the creation of new substring objects in each iteration. If `regionMatches` is used, the space complexity is O(1).

Trade-offs

Pros

  • Simple logic that directly translates the problem's core condition.

  • Easy to implement and understand.

  • Sufficiently fast for the given constraints (word.length <= 50).

Cons

  • Inefficient for very large strings due to repeated substring creation and comparison, leading to a quadratic time complexity in the worst case.

Solutions

class Solution:    def minimumTimeToInitialState(self, word: str, k: int) -> int: n = len(word) for i in range(k, n, k): if word[i:] == word[: - i]: return i // k return (n + k - 1) // k

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem