Minimum Window Substring | JavaScript
Tags: javascript, algorithms, leetcode, programming
Published: 2023-04-12 11:48:55

## Minimum Window Substring 
This is another approach and a faster solution from my previous one [Sliding Window using hashmaps](https://leetcode.com/problems/minimum-window-substring/solutions/3255923/javascript/).

You don't know what this problem is about?
See [here](https://leetcode.com/problems/minimum-window-substring/) 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](https://leetcode.com/problems/minimum-window-substring/solutions/3255923/javascript/), 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](https://tenor.com/view/mullvad-funny-bear-kuma-gif-25546456) 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
``` javascript
/**
 * @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) : "";
};
```