Sliding windows algorithm implementation for

by Konstantin Rouda

JavaScript

;(function () {
  "use strict";
   
  function minimumWindowSubstring (str, subStr) {
    const shortestWindow = [0, Infinity];
    const subStrCharsHashTable = {};
    let missingCharsCounter = subStr.length;
    let slowPointer = fastPointer = 0;
    
    // fill subStrCharsHashTable
    for(const char of subStr) {
      subStrCharsHashTable[char] = 0;
    };
    
    for(;fastPointer < str.length; fastPointer++) {
      const char = str[fastPointer];
      
      if(char in subStrCharsHashTable) {
        if(subStrCharsHashTable[char] === 0) {
          missingCharsCounter -= 1;
        }
        subStrCharsHashTable[char] += 1;
      };
      
      
      // shrink window
      while(missingCharsCounter === 0) {
        // updates result range if smaller than the previous one
        if((fastPointer - slowPointer) < (shortestWindow[1] - shortestWindow[0])) {
          shortestWindow[0] = slowPointer;
          shortestWindow[1] = fastPointer;
        }
        const char = str[slowPointer];
        if(char in subStrCharsHashTable) {
          subStrCharsHashTable[char] -= 1;
          if(subStrCharsHashTable[char] === 0) {
            missingCharsCounter += 1;
          }
        }
        slowPointer += 1;
      };
      
    };
    debugger; 
    return shortestWindow[1] === Infinity ? "" : str.slice(shortestWindow[0], shortestWindow[1] + 1);
  };
  
  
  console.log("minimumWindowSubstring: ", minimumWindowSubstring("afdergabcreyhrrabdervac", "abc"));
  
  
})();