문자열의 순열

var checkInclusion = function (s1, s2) {
  if (s1.length > s2.length) {
    return false;
  }

  const freqMap = {};
  let count = 0;
  let start = 0;
  let end = 0;

  for (let char of s1) {
    if (freqMap[char] === undefined) count++;
    freqMap[char] = (freqMap[char] || 0) + 1;
  }

  while (s2.length > end) {
    let nextChar = s2[end];

    if (freqMap[nextChar] !== undefined) {
      freqMap[nextChar]--;
      if (freqMap[nextChar] === 0) {
        count--;
      }
    }

    end++;
    if (count === 0) {
      return true;
    }

    if (end - start === s1.length) {
      let temp = s2[start];
      if (freqMap[temp] !== undefined) {
        freqMap[temp] += 1;
        if (freqMap[temp] > 0) count++;
      }
      start++;
    }
  }
  return false;
};

var checkInclusion_1 = function (s1, s2) {
  if (s1.length > s2.length) return false;
  let neededChar = {};
  for (let i = 0; i < s1.length; i++) {
    neededChar[s1[i]] = (neededChar[s1[i]] || 0) + 1;
  }
  /* 
    Now we have neededChar
    i.e neededChar={
        a:1,
        b:1
    }
    */
  let left = 0, //left pointer/index of the sliding window
    right = 0, //right pointer/index of the sliding window
    requiredLength = s1.length; //length of the substring required in s2

  // Now iterate 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 in 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 if our requiredLength becomes 0 it means we have found a match of the s2 substring
    // So we return true
    if (requiredLength === 0) return true;

    // If our window length is equal to s1 length (length of string to search in s2)
    // then 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]]++;

      left++;
    }
  }
  // If match was not found we return false
  return false;
};

console.log(checkInclusion("dc", "odicf"));

// ("trinitrophenylmethylnitramine");