567. Permutation in String

Link: https://leetcode.com/problems/permutation-in-string

Description: Given two strings s1 and s2, return true if s2 contains the permutation of s1.

Solution:

Using a sliding window approach, we can keep track of the characters in the current substring using a frequency count. We iterate through the string and add characters to the frequency count until the window is invalid. A window is invalid if the frequency count of the characters in the window matches the frequency count of the characters in s1. In this case, we return true. If the window is invalid, we decrease the frequency of the character at the start of the window and move the start of the window to the right. We continue this process until we reach the end of the string and return false if no valid window is found.

When the window is invalid, we decrease the frequency of the character at the start of the window and move the start of the window to the right. This ensures that the window is valid and the length of the window is calculated correctly.

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
  let start = 0
  let end = s1.length - 1

  while (end < s2.length) {
    const attempt = s2.slice(start, end + 1)
    const s1Hash = s1.split('').reduce((acc, char) => {
      if (!acc[char]) acc[char] = 0
      acc[char]++
      return acc
    }, {})

    for (const char of attempt) {
      if (s1Hash[char]) {
        s1Hash[char]--
      }
    }
    if (Object.values(s1Hash).every((v) => v === 0)) {
      return true
    } else {
      start++
      end++
    }
  }

  return false
}