Minimum Time to Revert Word to Initial State I – C++ Solution

Problem Description

Ah, the classic dilemma of wanting to revert a word back to its initial state. It’s like trying to unburn a toast or rewind a movie after realizing you’ve just watched the worst plot twist ever. The problem at hand is to determine the minimum number of operations required to revert a given string (or word) back to its original form after a series of transformations.

Imagine you have a word that has been altered by some mischievous gremlins, and you need to figure out how many times you need to hit the “undo” button (which, let’s be honest, is the most used button in any software). The catch? You can only revert a certain number of characters at a time, dictated by the integer k.

Solution Code


class Solution {
 public:
  int minimumTimeToInitialState(string word, int k) {
    const int n = word.length();
    const int maxOps = (n - 1) / k + 1;
    const vector z = zFunction(word);
    for (int ans = 1; ans < maxOps; ++ans)
      if (z[ans * k] >= n - ans * k)
        return ans;
    return maxOps;
  }

  vector zFunction(const string& s) {
    const int n = s.length();
    vector z(n);
    int l = 0;
    int r = 0;
    for (int i = 1; i < n; ++i) {
      if (i < r)
        z[i] = min(r - i, z[i - l]);
      while (i + z[i] < n && s[z[i]] == s[i + z[i]])
        ++z[i];
      if (i + z[i] > r) {
        l = i;
        r = i + z[i];
      }
    }
    return z;
  }
};

Approach Explanation

The code utilizes a clever technique known as the Z-algorithm, which helps in finding the longest substring that matches the prefix of the string. The zFunction computes an array where each element represents the length of the longest substring starting from that index that matches the prefix of the string.

The main function, minimumTimeToInitialState, calculates the maximum number of operations needed based on the length of the word and the allowed operations k. It checks if the substring can be reverted back to the original state using the precomputed Z-array.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the word. This is because both the Z-function and the main function iterate through the string a constant number of times.
Space Complexity: O(n) for storing the Z-array.

Real-World Example

Think of it like trying to get back to the original recipe of your favorite dish after a series of disastrous cooking attempts. Each time you try to fix it, you can only change a few ingredients at a time (that’s your k). The goal is to figure out how many attempts it will take to get back to that perfect dish you once had.