3031. Minimum Time to Revert Word to Initial State II

HardStringString MatchingHash FunctionRolling Hash
Leetcode Link

Problem Description

In this problem, you are provided a string word, which is indexed starting from 0, and an integer k. The goal is to determine the minimum time (measured in seconds) required for word to return to its original state following a set of operations that must be performed every second.

The operations are as follows:

  1. Remove the first k characters from the beginning of word.
  2. Append any k characters to the end of word. Note that the appended characters do not need to be the same as the ones that were removed.

The challenge is to carry out these operations such that after some time, the string word returns to exactly how it started. The requirement is to find the shortest time greater than zero for this to occur.

Intuition

To solve this problem, we will use a hash function to efficiently compare different segments of the string. Since we are repeatedly removing k characters from the front and appending k characters to the end, we need to check if after i increments of length k (where i is between k and the length of the string n), the substring from the start to the n-ith character is the same as the substring from the i+1th character to the end. If they are the same, it means that by performing the operation i/k times, we can get back to the initial state of the word.

Because string comparison can be costly for large strings, a rolling hash function is used to generate unique numerical values (hashes) for the substrings, which can be compared quickly. In this case, a specialized class Hashing is utilized to compute and store the hashes of all prefixes of the string and to query the hash values of any substrings in constant time.

By leveraging this efficient comparison method, we can iterate over possible lengths that are multiples of k and find the minimum time by checking the hash values for equivalence. If no such segment is found, the minimum time will be the length of the string divided by k, rounded up. This is the worst-case scenario where no part of the string can be reused, and we have to perform the operation sequentially for each block of k characters until the entire string is processed.

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

Which of the following is a min heap?

Solution Approach

The solution employs a Hashing class to create hash values for substrings of the input word. This class is initialized with the string, a base for the polynomial hash function, and a modulus to prevent integer overflow. Moreover, the class implements a query method to fetch the hash value of a substring between two indices. This technique is known as rolling hashing, which is a common approach to handling string comparisons efficiently.

Here is how the Hashing class operates:

  • During initialization, prefix hashes of all lengths and the corresponding powers of the polynomial base are precomputed. For a prefix of length i, the hash is computed as the sum of the hash of the previous prefix multiplied by the base, and the ASCII value of the current character, all taken modulo some large prime number to avoid overflow.

  • The query method retrieves hash values of substrings. It calculates a normalized hash value of a specified substring so that it can be directly compared with another substring's hash. The subtraction and multiplication by the inverse power of the base (modulo the chosen prime) ensure a consistent and unique hash value for equal substrings, despite different positions within the original string.

In the minimumTimeToInitialState function of the Solution class, we use the Hashing instance to compare segments of word after every batch of k operations:

  • We loop from k to n (where n is the length of word) in steps of k to check after how many operations the current state matches some previous state.

  • For each i, we invoke query twice: once for the substring from the start to n-i and once for the substring from i+1 to the end. If these two hashes are equal, it means that the i/k sequence of operations will return the word to its initial state.

  • If we do not find such a matching pair as we conclude the loop, it indicates that we have to perform the operations for every single block of k characters. Hence, the minimum time is computed as (n + k - 1) // k, which is the total length of the word divided by k, rounded up to account for any partial block at the end.

This approach guarantees an efficient comparison of substrings, significant time complexity reduction, and accurate determination of the minimum time to revert the word to its initial state.

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

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Example Walkthrough

Let's consider a simple example to illustrate the solution approach. Suppose the given word is word = "algorithm" and k = 2. The goal is to find the minimum time to return word to its original state by performing the predefined operations as described.

  1. First, we initialize a Hashing class with word = "algorithm", a base (chosen to be any arbitrary prime number for the sake of the hashing function), and a modulus (again, a large prime number to avoid overflow). This class precomputes hashes for all the prefixes of "algorithm" and powers of the base.

  2. After initializing the Hashing class, we proceed with the main function, minimumTimeToInitialState. In this example, n = 9 (length of "algorithm").

  3. We start looping from i = k = 2 to n = 9 in steps of k. With each step, we check if the word can be returned to its initial state.

  4. When i = 2, we remove "al" from the start and consider adding any two characters at the end. However, comparing the remaining string "gorithm" with any other segment of the same length using our hash values, we notice that there is no match, so we continue.

  5. We increment i by k to check the next possible state after every k operations. When i = 4, the string becomes "orithm", which does not match any other segments, so we continue.

  6. This process is repeated until i = 8. Here we are left with "gm" after removing "algorithm" - "algorit". If we append "al" (or any other two characters), we would end up with "gmal" at the end of the string, which does not match the original substring "algo". Hence, there is still no match.

  7. Since we have tested all increments of k without finding a matching segment, the worst-case scenario applies. The minimum time is then computed as (n + k - 1) // k. For our example, (9 + 2 - 1) // 2 = 5. This means the operations must be performed 5 times to ensure that every part of the string "algorithm" has cycled through, and the word returns to its original state.

In conclusion, this example demonstrates the steps taken to determine the minimum time to get back the initial word, making use of rolling hashing for efficient substring comparison and a systematic check of feasible solutions according to the constraints of the problem.

Solution Implementation

1class RollingHash:
2    # Using `__slots__` for memory efficiency by declaring the only attributes of the class.
3    __slots__ = ["modulus", "hash_list", "power_list"]
4
5    def __init__(self, string: str, base: int, modulus: int):
6        """Initializes the rolling hash with the given string, base, and modulus."""
7        self.modulus = modulus
8        self.hash_list = [0] * (len(string) + 1)
9        self.power_list = [1] * (len(string) + 1)
10      
11        # Precompute the hash values for all prefixes and the powers of base.
12        for i in range(1, len(string) + 1):
13            self.hash_list[i] = (self.hash_list[i - 1] * base + ord(string[i - 1])) % modulus
14            self.power_list[i] = (self.power_list[i - 1] * base) % modulus
15
16    def query(self, left: int, right: int) -> int:
17        """Computes and returns the hash value for the substring from left to right (1-indexed)."""
18        return (self.hash_list[right] - self.hash_list[left - 1] * self.power_list[right - left + 1]) % self.modulus
19
20
21class Solution:
22    def minimumTimeToInitialState(self, word: str, k: int) -> int:
23        """Calculates the minimum number of operations to return to the initial state of the string."""
24        # Initialize the RollingHash object with the word, a chosen base, and a chosen modulus.
25        rolling_hash = RollingHash(word, 13331, 998244353)
26        word_length = len(word)
27        # Try to find a smaller length of word that can be repeated to match the original word.
28        for i in range(k, word_length, k):
29            # If the prefix and the suffix hashes match, we've found a repeatable pattern.
30            if rolling_hash.query(1, word_length - i) == rolling_hash.query(i + 1, word_length):
31                # Return the quotient of dividing by k as the minimum operations count.
32                return i // k
33        # If no pattern is found, the word cannot be compressed and needs to be spelled out.
34        return (word_length + k - 1) // k
35
1class StringHashing {
2    private final long[] powersOfBase;
3    private final long[] hashPrefixes;
4    private final long modulus;
5
6    /**
7     * Constructor to initialize the data for hashing the given string.
8     * @param word the input string to be hashed.
9     * @param base the base for polynomial rolling hash function.
10     * @param mod the modulus to be used for hashing to keep values within range.
11     */
12    public StringHashing(String word, long base, int mod) {
13        int length = word.length();
14        powersOfBase = new long[length + 1];
15        hashPrefixes = new long[length + 1];
16        this.modulus = mod;
17        powersOfBase[0] = 1;
18
19        // Pre-compute powers of the base and the prefix hashes of 'word'
20        for (int i = 1; i <= length; i++) {
21            powersOfBase[i] = powersOfBase[i - 1] * base % modulus;
22            hashPrefixes[i] = (hashPrefixes[i - 1] * base +
23                (word.charAt(i - 1) - 'a')) % modulus;
24        }
25    }
26
27    /**
28     * Queries the hash value for the substring of the word from index l to r.
29     * @param l the starting index of the substring (1-indexed).
30     * @param r the ending index of the substring (1-indexed).
31     * @return the hash value of the specified substring.
32     */
33    public long query(int l, int r) {
34        return (hashPrefixes[r] - hashPrefixes[l - 1] * powersOfBase[r - l + 1] % modulus + modulus) % modulus;
35    }
36}
37
38class Solution {
39    /**
40     * Calculates the minimum amount of time to return to the initial state of a
41     * circular word when we can move at every k letters.
42     * @param word the word to be checked in circular fashion.
43     * @param k the step size of the movement.
44     * @return the minimum number of steps to return to the initial state.
45     */
46    public int minimumTimeToInitialState(String word, int k) {
47        StringHashing stringHashing = new StringHashing(word, 13331, 998244353);
48        int length = word.length();
49
50        // Loop over the word at intervals of k to find the first matching hash.
51        for (int i = k; i < length; i += k) {
52            // Compare the hashes of the substring from start to the i-th character
53            // and the substring from the i-th character to the end to check if they match.
54            if (stringHashing.query(1, length - i) == stringHashing.query(i + 1, length)) {
55                return i / k;
56            }
57        }
58
59        // If no matching hash is found, return the ceiling of length/k.
60        return (length + k - 1) / k;
61    }
62}
63
1#include <vector>
2#include <string>
3
4class Hashing {
5private:
6    std::vector<long long> powers_of_base;
7    std::vector<long long> hash_values;
8    long long modulus;
9
10public:
11    // Constructor which initializes the hash values and powers for a given string
12    Hashing(const std::string& word, long long base, long long mod) {
13        int n = word.size();
14        powers_of_base.resize(n + 1);
15        hash_values.resize(n + 1);
16        powers_of_base[0] = 1;
17        modulus = mod;
18        for (int i = 1; i <= n; ++i) {
19            powers_of_base[i] = (powers_of_base[i - 1] * base) % modulus;
20            hash_values[i] = (hash_values[i - 1] * base + word[i - 1] - 'a') % modulus;
21        }
22    }
23
24    // Queries the hash value of a subsequence defined by its left and right indices
25    long long query(int left, int right) {
26        long long result = (hash_values[right] - hash_values[left - 1] * powers_of_base[right - left + 1] % modulus + modulus) % modulus;
27        return result;
28    }
29};
30
31class Solution {
32public:
33    // Method to determine the minimum time to reach the initial state
34    int minimumTimeToInitialState(const std::string& word, int k) {
35        Hashing hashing(word, 13331, 998244353);
36        int n = word.size();
37        // Iterate through the string at intervals of `k` to check for repeats
38        for (int i = k; i < n; i += k) {
39            // If the hash value of the string from start to `n-i` is equal to
40            // the hash value of the string from `i+1` to the end,
41            // return the number of moves
42            if (hashing.query(1, n - i) == hashing.query(i + 1, n)) {
43                return i / k;
44            }
45        }
46        // If no repeating pattern is found, return this calculation
47        return (n + k - 1) / k;
48    }
49};
50
1// Import array and string functionalities
2import { vector } from 'prelude-ts';
3
4// Initialize power bases and hash values arrays along with the modulus value
5let powersOfBase: vector<number>;
6let hashValues: vector<number>;
7let modulus: number;
8
9// Function to initialize the hash values and powers for a given string, base, and modulus
10function initializeHashing(word: string, base: number, mod: number): void {
11    const n: number = word.length;
12    powersOfBase = vector.of<number>(1);
13    hashValues = vector.of<number>(0);
14    modulus = mod;
15    for (let i = 1; i <= n; i++) {
16        powersOfBase = powersOfBase.append(powersOfBase.get(i - 1) * base % modulus);
17        hashValues = hashValues.append(hashValues.get(i - 1) * base + word.charCodeAt(i - 1) - 'a'.charCodeAt(0) % modulus);
18    }
19}
20
21// Function to query the hash value of a substring given by its start and end indices
22function queryHash(left: number, right: number): number {
23    const result: number = (hashValues.get(right) - hashValues.get(left - 1) * powersOfBase.get(right - left + 1) % modulus + modulus) % modulus;
24    return result;
25}
26
27// Function to determine the minimum time to reach the initial state for a given string and steps count
28function minimumTimeToInitialState(word: string, k: number): number {
29    initializeHashing(word, 13331, 998244353);
30    const n: number = word.length;
31    // Iterate through the string at intervals of `k` to check for repeats
32    for (let i = k; i < n; i += k) {
33        // If the hash value of the substring from start to `n - i` is equal to
34        // the hash value of the substring from `i + 1` to the end, return the number of moves
35        if (queryHash(1, n - i) === queryHash(i + 1, n)) {
36            return i / k;
37        }
38    }
39    // If no repeating pattern is found, return this calculation
40    return Math.ceil(n / k);
41}
42
43// Example usage of the function to find minimum time
44const word = "abcdabcd";
45const k = 2;
46console.log(minimumTimeToInitialState(word, k)); // Output should correspond to the minimum number of time steps
47
Not Sure What to Study? Take the 2-min Quiz：

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Time and Space Complexity

Time Complexity

The time complexity of the Hashing class constructor is O(n), where n is the length of the string s. This is because the constructor iterates once over all the characters of the string to calculate the hash values and powers of the base.

The time complexity of the query method inside the Hashing class is O(1). The method performs a constant number of arithmetic operations, regardless of the length of the substring.

The minimumTimeToInitialState method of the Solution class has a loop that runs from k to n in steps of k, resulting in about n/k iterations. Inside each iteration, it calls the query method twice, which is O(1) per call. Hence, the time spent in the loop is O(n/k).

Therefore, the total time complexity of the minimumTimeToInitialState method is O(n) + O(n/k) = O(n) when considering the constructor and the loop together.

Space Complexity

The space complexity of the Hashing class is O(n) because of the storage of the hash values and powers of the base in lists h and p, both of which have a length of n + 1.

The space complexity of the minimumTimeToInitialState method in the Solution class is O(n), coming from the Hashing class it instantiates. There are no other significant data structures taking up space, as the loop variables and comparison results use constant space.

Overall, the space complexity of the entire code is O(n).

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

Fast Track Your Learning with Our Quick Skills Quiz:

How many ways can you arrange the three letters A, B and C?

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 👨‍🏫