## 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) : "";
};
```

## Top comments (0)