PermutationinString.js

/**
 *  @name The-Sliding-Window Algorithm is primarily used for the problems dealing with linear data structures like Arrays, Lists, Strings etc.
 *  These problems can easily be solved using Brute Force techniques which result in quadratic or exponential time complexity.
 *  Sliding window technique reduces the required time to linear O(n).
 *  @see [The-Sliding-Window](https://www.geeksforgeeks.org/window-sliding-technique/)
 */
/**
 * @function PermutationinString
 * @description Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
 * @param {String} s1 - The input string
 * @param {String} s2 - The input string
 * @return {boolean} - Returns true if s2 contains a permutation of s1, or false otherwise.
 */

export function PermutationinString(s1, s2) {
  if (s1.length > s2.length) return false
  let start = 0
  let end = s1.length - 1
  const s1Set = SetHash()
  const s2Set = SetHash()
  for (let i = 0; i < s1.length; i++) {
    s1Set[s1[i]]++
    s2Set[s2[i]]++
  }
  if (equals(s1Set, s2Set)) return true
  while (end < s2.length - 1) {
    if (equals(s1Set, s2Set)) return true
    end++
    const c1 = s2[start]
    const c2 = s2[end]
    if (s2Set[c1] > 0) s2Set[c1]--
    s2Set[c2]++
    start++
    if (equals(s1Set, s2Set)) return true
  }
  return false
}
function equals(a, b) {
  return JSON.stringify(a) === JSON.stringify(b)
}

function SetHash() {
  const set = new Set()
  const alphabets = 'abcdefghijklmnopqrstuvwxyz'
  for (let i = 0; i < alphabets.length; i++) {
    set[alphabets[i]] = 0
  }
  return set
}

// Example 1:
// Input: s1 = "ab", s2 = "eidbaooo"
// Output: true
// Explanation: s2 contains one permutation of s1 ("ba").

// Example 2:
// Input: s1 = "ab", s2 = "eidboaoo"
// Output: false