Using Sliding Window
So the brute force approach isn't the best. Luckily, we can utilize the sliding window technique. We will break it down, but first let's observe the entire solution with comments. s
is the string, and req_chars
is the substring containing all the required characters.
xxxxxxxxxx
74
console.log(minWindow("abcalgosomedailyr", "ad"));
function minWindow(s, reqChars) {
// hash to keep account of how many required characters we've checked off
// each key will represent a character in reqChars
// we preset each to 1 and will look to lower it to 0 when each is fulfilled
const hash = {};
for (let c of reqChars) {
hash[c] = 1;
};
// trackers that we need
// this is a counter to measure string length against
let counter = reqChars.length;
let begin = 0;
let end = 0;
let substrSize = s.length + 1;
let head = 0;
while (end < s.length) {
// continue running while there's more elements in `s` to process
if (s[end] in hash) { // we've found a letter we needed to fulfill
// modify the length counter, we can use this as part of our substring
if (hash[s[end]] > 0) {
counter -= 1;
}
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment