Scale Engineer

Minimum Time to Revert Word to Initial State II

Hard
#2699Time: O(N^2 / k). The loop for `t` runs up to `N/k` times. In each iteration, we compare strings of length `N - t*k`. The total number of character comparisons is the sum `(N-k) + (N-2k) + ...`, which is on the order of `O(N^2 / k)`. In the worst case, when `k=1`, the complexity is `O(N^2)`.Space: O(1). We are not using any extra space that scales with the input size `n`. `regionMatches` compares parts of the existing string in-place.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 <= 106
  • 1 <= k <= word.length
  • word consists only of lowercase English letters.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We iterate through the number of operations t starting from 1. For each t, we calculate the number of characters removed from the prefix, which is i = t * k. We then check if the remaining suffix of the original word, word.substring(i), is identical to a prefix of the original word of the same length, word.substring(0, n-i). If they match, we've found the minimum time t. If we iterate through all possible t where t*k < n and find no match, the answer is the smallest t for which t*k >= n, which is ceil(n/k).

Algorithm

  1. Get the length of the word, n.
  2. Loop through time t starting from 1.
  3. In each iteration, calculate the number of characters that would have been removed, i = t * k.
  4. If i is greater than or equal to n, it means we have checked all possibilities where a non-empty suffix of the original word remains. The minimum time is t in this case, so we return t.
  5. Otherwise, we check if the suffix of word starting at index i is equal to the prefix of word of the same length (n-i). We can use word.regionMatches(0, word, i, n - i) for an efficient comparison that avoids creating new string objects.
  6. If they are equal, we have found the smallest t that works, so we return t.
  7. If the strings are not equal, we continue to the next value of t.

Walkthrough

The core idea is to test each possible time t=1, 2, 3, ... sequentially. For a given time t, t*k characters are removed from the beginning of the word. The length of the word is n. The remaining part of the word is the suffix starting at index t*k, and its length is n - t*k. To revert to the initial state, this remaining suffix must be a prefix of the original word. So, we check if word[i...n-1] equals word[0...n-i-1]. The first t > 0 for which this condition holds is our answer. If no such t exists for t*k < n, it means we can only revert the word after removing all of its characters. The time for this is ceil(n/k), which can be calculated using integer arithmetic as (n + k - 1) / k. The loop for t will naturally arrive at this value if no earlier match is found.

class Solution {    public int minimumTimeToInitialState(String word, int k) {        int n = word.length();        for (int t = 1; ; ++t) {            int i = t * k;            if (i >= n) {                return t;            }            // Check if suffix starting at i matches prefix of same length            if (word.regionMatches(0, word, i, n - i)) {                return t;            }        }    }}

Complexity

Time

O(N^2 / k). The loop for `t` runs up to `N/k` times. In each iteration, we compare strings of length `N - t*k`. The total number of character comparisons is the sum `(N-k) + (N-2k) + ...`, which is on the order of `O(N^2 / k)`. In the worst case, when `k=1`, the complexity is `O(N^2)`.

Space

O(1). We are not using any extra space that scales with the input size `n`. `regionMatches` compares parts of the existing string in-place.

Trade-offs

Pros

  • Simple to understand and implement.

  • It correctly solves the problem for small inputs.

Cons

  • The time complexity is high, making it unsuitable for large constraints.

  • It will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits.

Solutions

class Hashing { private final long [] p ; private final long [] h ; private final long mod ; public Hashing ( String word , long base , int mod ) { int n = word . length (); p = new long [ n + 1 ]; h = new long [ n + 1 ]; p [ 0 ] = 1 ; this . mod = mod ; for ( int i = 1 ; i <= n ; i ++) { p [ i ] = p [ i - 1 ] * base % mod ; h [ i ] = ( h [ i - 1 ] * base + word . charAt ( i - 1 ) - 'a' ) % mod ; } } public long query ( int l , int r ) { return ( h [ r ] - h [ l - 1 ] * p [ r - l + 1 ] % mod + mod ) % mod ; } } class Solution { public int minimumTimeToInitialState ( String word , int k ) { Hashing hashing = new Hashing ( word , 13331 , 998244353 ); int n = word . length (); for ( int i = k ; i < n ; i += k ) { if ( hashing . query ( 1 , n - i ) == hashing . query ( i + 1 , n )) { 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