Minimum Window Substring | JavaScript

Minimum Window Substring

This is another approach and a faster solution from my previous one Sliding Window using hashmaps.

You don't know what this problem is about?
See here the problem description, and try to solve it before reading this solution.

Solution

We will use the Sliding Window method

We will have an array of 58 Zeros holding the ASCII code for every letter from A to z.
We have 52 letters in total but need 6 more "useless" zeros because there is a distance of 6 in between the ascii codes of 'Z' and 'a' (No need to make it more complex).
In the beginning, neededCharsArray holds the total number of our chars in string t. So for t='ABByzzzzz' neededCharsArray will be like: [1,2,0,0,0...,0,0,0,1,5]

Similar to my first solution on leetcode, we will have two pointers, left and right, which will point to the edges of our sliding window.

For every char in s we will check if neededCharsArray holds a value greater than zero. This means it's a wanted char, and because we found one we will reduce missingChars by one.

Bear in mind that:

For every char of s we decrease it's corresponding value in neededCharsArray by one.

So, while having the index of this char to our right index, we keep moving our left index to the right and closer to the right index, narrowing our window (trying to find a better alternative).

Bear in mind that:

While we're sliding our left index we increase it's corresponding value in neededCharsArray by one.

Not bored yet?

Having those bears in mind, we know that every char of s that is of no interest will result in a value <=0 in our neededCharsArray. But every char of s that is wanted and exists in t, will result in a value >=0 in our neededCharsArray.

We will get into our while statement when missingChars is equal to zero. This means that the corresponding values of our wanted chars in neededCharsArray will be zero. All of them! There might be some other negative values for unwanted chars that exist in s and not in t. Other zeros may appear too (for chars that don't exist in s and t).

In our while statement we increase our left index. So in the next iteration, if the left index points to a wanted char, we will have a positive value in our neededCharsArray, this will break our while loop ( because the 2nd if statement increases missingChars) and will go out to our for loop, increasing our right index, checking the next one, searching for our missing char. Until we reach the last one.

Complexity

Time complexity:
O(n)

Space complexity:
O(1)

Code

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
const minWindow = (s, t) => {
  if (!s.length || !t.length || s.length < t.length) return "";
  if (s === t) return s;

  // 26 zeros for A-Z, 26 for a-z, and 6 for the diff from 'Z' (090) to 'a' (097)
  let neededCharsArray = new Array(58).fill(0);
  let firstCharCode = "A".charCodeAt(0); // A - A = 0; A - z = 57

  for (let c of t) {
    neededCharsArray[c.charCodeAt(0) - firstCharCode]++;
  }

  let missingChars = t.length;
  let result = [-Infinity, Infinity];
  let left = 0;

  for (let right = 0; right < s.length; right++) {
    if (neededCharsArray[s.charCodeAt(right) - firstCharCode] > 0) {
      missingChars--;
    }
    neededCharsArray[s.charCodeAt(right) - firstCharCode]--;
    while (missingChars === 0) {
      if (result[1] - result[0] > right - left) {
        result[0] = left;
        result[1] = right;
      }
      neededCharsArray[s.charCodeAt(left) - firstCharCode]++;
      if (neededCharsArray[s.charCodeAt(left) - firstCharCode] > 0) {
        missingChars++;
      }
      left++;
    }
  }

  return result[1] !== Infinity ? s.slice(result[0], result[1] + 1) : "";
};