Minimum Window Substring
Given two strings s and t of lengths m and n respectively, return the minimum window
substringof 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.