# Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return *the ***minimum window**

**substring***of *s* such that every character in *t* (***including duplicates***) is included in the window*. If there is no such substring, return *the empty string *"".

The testcases will be generated such that the answer is **unique**.

```
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
if (t.length > s.length) return '';
const neededChars = {};
for (let char of t) {
neededChars[char] = (neededChars[char] || 0) + 1;
}
let left = 0;
let right = 0;
let neededLength = Object.keys(neededChars).length;
let substring = '';
while (right < s.length) {
const rightChar = s[right];
neededChars[rightChar]--;
if (neededChars[rightChar] === 0) neededLength--;
while (neededLength === 0) {
if (!substring || substring.length > right - left + 1) {
substring = s.slice(left, right + 1);
}
const leftChar = s[left];
// If the leftChar in charMap is at exactly 0 before being
// incremented, we now need more leftChars so that its count
// in charMap goes down to exactly 0
if (neededChars[leftChar] === 0) {
neededLength++;
}
neededChars[leftChar]++;
left++;
}
right++;
}
return substring;
};
```

Sliding window problems all follow a similar pattern

## Related Problems

Given a string **S** and an integer **K**, return *the length of the longest substring of* **S** *that contains at most* **K** **distinct*** characters*.

Given an integer array nums, you need to find one **continuous subarray** such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return *the shortest such subarray and output its length*.

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy **all of the following rules**:

Each of the digits 1-9 must occur exactly once in each row.

Each of the digits 1-9 must occur exactly once in each column.

Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

You are given two integer arrays nums1 and nums2, sorted in **non-decreasing order**, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

**Merge** nums1 and nums2 into a single array sorted in **non-decreasing order**.

The final sorted array should not be returned by the function, but instead be *stored inside the array *nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.