Sliding Window

투포인터 알고리즘과 비슷하지만 일정 간격을 두고 두 포인터가 끝을향해 나아간다는 점에서 다르다

reetCode 567번 문제

/**
 *  Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
    In other words, return true if one of s1's permutations is the substring of s2.
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
  // If s1 is larget than s2 then match is not possible
  if (s1.length > s2.length) return false;
  let neededChar = {}; // To Store the frequency/count of required string s1
  for (let i = 0; i < s1.length; i++) {
    // Initially neededChar[s1[i]] will be undefined and
    // undefined || 0- will return 0. So we increment it by 1.
    neededChar[s1[i]] = (neededChar[s1[i]] || 0) + 1;
  }
  let left = 0; // left pointer/ index of the sliding window
  let right = 0; // right pointer/ index of the sliding window
  let requiredLength = s1.length; // length of the substring required in s2
  // Now interate until the right index of window is lesser than length of s2
  while (right < s2.length) {
    // If we found s2 character in s1 i.e neededChar then we decrease requiredLength
    if (neededChar[s2[right]] > 0) requiredLength--;
    // Since we have encountered new char i.e s2[right] we decrease it's
    // count in neededChar even if it is not present in neededChar because we only
    // care about neededChars
    neededChar[s2[right]]--;
    right++; // window is incremented by 1 step
    // Now it out requiredLength becomes 0 it means we have found a match of the
    // s2 substring. So we reuturn true.
    if (requiredLength === 0) return true;
    // If out window length is equal to s1 length the we have to remove left element
    // of window i.e left++ and add new element from right will be added in next
    // iteration
    if (right - left === s1.length) {
      // if the left element we are removing was a required character then we
      // increase requiredLength because that element will no longer be the part
      // of sliding window
      if (neededChar[s2[left]] >= 0) requiredLength++;
      // We will also increase the count of left element removed from window
      neededChar[s2[left]]++;
      // And finally we will decrease the window size by 1 from left i.e left
      left++;
    }
  }
  // if match was not found we return false
  return false;
};

윈도우 슬라이딩 이라는 알고리즘을 처음 접해본 문제이다.....
접근법과 해결책은 비슷하게 생각해 냈는데 그걸 구현하는데 문제가 많아 결국 솔루션을 보고 말았다.
가만 보니 기본적인 슬라이딩 윈도우 문제가 아닌가 싶다 좀 더 열심히 해야겠다.

reference from https://leetcode.com/problems/permutation-in-string/solutions/1761929/easy-js-sliding-window-o-n-commented/