Sliding Window(hard): Premutations in a string

premutationsInAstring.js

/*
Desc: Given a string and a pattern, find out if the string contains any permutation of the pattern.

Input: str=string, pattern=string
Output: boolean

Steps:

1. We'll iterate through the array
2. Once the window has 3 elements, we'll check if what's in the sliding window is equal to the pattern
  - else, shrink the window
3. If the check return true, exit the function. 
4. If we reached the end of the array, return false
*/

// Time: O(n)
// Space: O(log n) i think
const helper = (substring, pattern) => {
  const obj = {};
  for (let i = 0; i <= pattern.length; i++) {
    if (pattern.includes(substring[i])) {
      obj[substring[i]] = (obj[substring[i]] || 0) + 1;
    }
  }

  const isPremutation = Object.values(obj).reduce((acc, e) => acc + e, 0)
  
  return isPremutation === pattern.length;
};

// helper('bcdxabcdy', 'bcdyabcdx') // true 
// helper('bca', 'abc') // true
// helper('di', 'dc') // false

// Time: O(N * M) — could be optimized to O(N + M)
// Space: O(n)
const premutationInAstring = (str, pattern) => {
  let windowStart = 0
  
  if (str.length === pattern.length) return helper(str, pattern)
  
  for (let windowEnd = 0; windowEnd < str.length; windowEnd++) {    
    if ((windowEnd - windowStart) === pattern.length) {
      if (helper(str.slice(windowStart, windowEnd), pattern)) {
        return true
      }
    }
    
    if ((windowEnd - windowStart + 1) > pattern.length) {
      windowStart += 1
    }
  }
  
  return false
};


premutationInAstring('oidbcaf', 'abc') // true
premutationInAstring('odicf', 'dc') // false
premutationInAstring('bcdxabcdy', 'bcdyabcdx') // true
premutationInAstring('aaacb', 'abc') // true
premutationInAstring('cidc', 'cdc') // false
premutationInAstring('cidc', 'id') // true