3029. Minimum Time to Revert Word to Initial State I

MediumStringString MatchingHash FunctionRolling Hash
Leetcode Link

Problem Description

In this problem, we have a string word, which is indexed starting from 0, and an integer k. The goal is to determine the minimum time to bring word back to its original state through a series of operations performed every second. Each second, we need to:

  1. Remove the first k characters (sub-string) from word.
  2. Append any k characters at the end of word.

The added twist is that the characters you add don't have to be the ones you just removed. The requirement is to perform both operations simultaneously, and we need to find the minimum number of seconds necessary to revert word to its initial state.

Intuition

The intuition behind the solution relies on discovering a pattern in the transformation of the string word. At each operation, we take a block of k characters from the front and append k characters at the back. To find when the word returns to its original state, we should look for a repetition in the string that matches the start of the string.

The key observation is that if after i operations (where i is a multiple of k), the part of the string after k*i characters matches the original string starting from the 0th index up to n-k*i, where n is the length of word, then the word has come back to its original state. This would mean every k*i characters in the string can be cycled through removals and additions to achieve the initial state of the string.

To implement this idea, we iterate through the string, checking at each multiple of k if the postfixed string word[k*i:] is the same as the start of the original string word[:-k*i]. If we find a match, then dividing the matching index by k gives us the total operations (seconds) taken to get back to the starting state. If we don't find any such match, then the smallest number of operations needed would involve going through the entire string once, hence (n + k - 1) // k operations.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search can be used to find whether two components in a graph are connected.

Solution Approach

The implementation of the solution is simple and direct. It follows the steps outlined in the Reference Solution Approach, utilizing a single loop and basic string comparison to find the cycle that brings the word back to its initial state.

No complex data structures are needed for this approach. The main algorithm pattern in place here is enumeration, which is a straightforward technique to iterate through the possibilities until the solution is found.

The process of the algorithm is as follows:

  1. Calculate the length of the string word and store it in a variable n.
  2. Use a for loop to iterate over the string, starting from k and continuing in increments of k until the end of the string n.
  3. Inside the loop, check if the substring of word from the current index i to the end (word[i:]) matches the substring from the start of word to the n - i index (word[:-i]). This represents that after removing and appending k characters i // k times, word has returned to its initial state.
  4. If the condition in step 3 is true, immediately return i // k as the minimum time.
  5. If the loop completes without finding a match, then the word does not revert to its initial state until we have gone through all its characters at least once. Thus we return (n + k - 1) // k, which accounts for the case where the last set of characters to revert might not be a full k characters in length.

The return (n + k - 1) // k line handles the edge case that when we're left with fewer than k characters at the end, we still need an extra operation to complete the cycle.

This procedure finds the minimum number of operations necessary to restore word to its original state, by systematically checking for cycles in the string formed by the series of operations defined in the problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Example Walkthrough

Let's consider a simple example to illustrate the solution approach using a string word = "abcabc" and k = 3.

Step by step process:

  1. We calculate the length n of word, which in this case is 6.
  2. Now, k is 3, so we will be taking and appending blocks of 3 characters at each operation. We start iterating with a for loop beginning from k (3 in this case) and increment by k with each iteration.
  3. At each iteration i (which is a multiple of k), we compare the substring of word from index i to the end, word[i:], with the substring from the start of word to the index n-i, word[:n-i].
    • At i = 3, we take the substring word[i:] which is "abc", and compare it with word[:n-i], which is also "abc". They match, indicating that after 1 operation (removing "abc" from the start and appending "abc" to the end), the word will return to its original state.
  4. Since we have found a match, we return i // k, which is 3 // 3 or 1 in this case.

Therefore, in this example, it takes a minimum of 1 operation to bring word back to its original state.

No further iterations are necessary because we found the cycle length in this example during the first iteration. If the word did not revert to its initial state by the end of the iteration through its length, we would have used the formula (n + k - 1) // k to determine the minimum number of operations required.

Solution Implementation

1class Solution:
2    def minimum_time_to_initial_state(self, word: str, k: int) -> int:
3        # Calculate the length of the word
4        word_length = len(word)
5      
6        # Iterate over the word, checking substrings of length multiples of k
7        for i in range(k, word_length, k):
8            # Check if the substring from the current position to the end
9            # matches the substring from the beginning to the complementary position
10            if word[i:] == word[:-i]:
11                # If yes, the minimum number of times to reach the initial state can be calculated
12                # by dividing the current index by k. Return this value.
13                return i // k
14      
15        # If no pattern was found, calculate and return the ceiling division of the
16        # word's length by k, as the number of times needed to process the entire string
17        return (word_length + k - 1) // k
18
19# Example of usage:
20# solution = Solution()
21# result = solution.minimum_time_to_initial_state("abcabcabc", 3)
22# print(result)  # Output will be 1, since "abcabcabc" returns to the initial "abc" after 1 iteration of size 3
23
1class Solution {
2    public int minimumTimeToInitialState(String word, int k) {
3        // Calculate the length of the word
4        int wordLength = word.length();
5      
6        // Loop through the word in increments of 'k'
7        for (int i = k; i < wordLength; i += k) {
8            // Check if the substring starting from index 'i' to the end of the word
9            // is equal to the substring from the beginning of the word to length 'wordLength - i'
10            if (word.substring(i).equals(word.substring(0, wordLength - i))) {
11                // If they are equal, return the minimum number of times 'k' fits into 'i'
12                return i / k;
13            }
14        }
15      
16        // If no such substring is found that matches the condition,
17        // return the minimum number of times to cover the entire word plus the remaining characters,
18        // also accounting for partially filling the last segment.
19        return (wordLength + k - 1) / k;
20    }
21}
22
1class Solution {
2public:
3    // Function to determine the minimum number of time units to return a string to its initial state
4    int minimumTimeToInitialState(string word, int k) {
5        int n = word.size(); // Store the length of the input string
6
7        // Loop through the string in steps of 'k'
8        for (int i = k; i < n; i += k) {
9            // Check if the substring starting at index 'i' is equal to the substring starting at the beginning of the word
10            // with the same length. This indicates that the pattern repeats and the initial state is reached.
11            if (word.substr(i) == word.substr(0, n - i)) {
12                // If a match is found, return the number of steps taken to reach the initial state
13                return i / k;
14            }
15        }
16
17        // If no repeating pattern is found that matches the criteria, return the ceiling of word size divided by 'k'
18        // This implies performing the operation on the whole string until the initial state is reached.
19        return (n + k - 1) / k;
20    }
21};
22
1/**
2 * Calculates the minimum time to return to the initial state of a word by deleting every k-th character.
3 * The process repeats until a previous state is formed or all characters are deleted.
4 * 
5 * @param {string} word - The word to be reverted to its initial state.
6 * @param {number} k - The step size indicating after how many characters a deletion occurs.
7 * @returns {number} - The number of steps required to return to the initial state.
8 */
9function minimumTimeToInitialState(word: string, k: number): number {
10    // n represents the length of the word.
11    const n = word.length;
12
13    // Loop through the word, incrementing by k each time.
14    for (let i = k; i < n; i += k) {
15        // Check if the substring from the current position 'i' to the end
16        // is equal to the substring from the start to the length of the word minus 'i'.
17        // If they are equal, the word can be reverted to its previous state in i/k steps.
18        if (word.slice(i) === word.slice(0, -i)) {
19            return Math.floor(i / k);
20        }
21    }
22
23    // If no previous state is found, calculate the maximum number of steps
24    // required to delete all characters based on the step size 'k'.
25    // The expression ensures the result is rounded up to account for the last remaining characters.
26    return Math.floor((n + k - 1) / k);
27}
28
Not Sure What to Study? Take the 2-min Quiz：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Time and Space Complexity

The time complexity of the provided code is O(n^2). In the worst case, the for loop runs for n/k iterations, and in each iteration, it performs a substring operation and string comparison with a complexity of O(n) leading to a total of O(n * (n/k)) which simplifies to O(n^2) because k is a constant and does not grow with n. Substring operations involve creating new strings which take O(n) time each.

The space complexity is O(n) primarily due to the substring operation within the loop that potentially creates a new string of size n at each iteration. Although only one substring is kept in memory at a time, its size could be as large as the original word, which means it directly scales with the input size n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫