## 567. Permutation in String

>[567. Permutation in String
](https://leetcode.com/problems/permutation-in-string/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
- Use hashmap: count the frequency of each character
- in s1
- in the substring of s2 (the substring's length is s1.length)
- Use sliding window
- the window's width is fixed

:::spoiler Code

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function(s1, s2) {
    const counter1 = new Map();
    for (const char of s1) {
      counter1.set(char, (counter1.get(char) || 0) + 1);
    }

    let left = 0;
    let right = s1.length - 1;

    const counter2 = new Map();
    for (let i = 0; i < right; i++) {
      const char = s2[i];
      counter2.set(char, (counter2.get(char) || 0) + 1);
    }

    while (right < s2.length) {
      const char = s2[right];
      counter2.set(char, (counter2.get(char) || 0) + 1);

      let isEqual = true;
      for (const [char, count] of counter1.entries()) {
        if (counter2.get(char) !== count) {
          isEqual = false;
          break;
        }
      }
      if (isEqual) {
        return true;
      }

      // move the window right
      const leftChar = s2[left];
      counter2.set(leftChar, counter2.get(leftChar) - 1);
      if (counter2.get(leftChar) === 0) {
        counter2.delete(leftChar);
      }

     
      left++;
      right++;
    }

    return false;
};

:::

<hr/>

### Sol

Sliding window technique(Fixed-size).
Time complexity: O(26 * N)
- Create frequency maps for s1 and the current window in s2.
- Check if frequencies match, if true 🥳🥳🥳
- If not, adjust the pointers and the frequency for the sliding window

:::spoiler Code

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
function objectsMatch(obj1, obj2) {
    for (let key in obj1) {
        if (obj1[key] !== obj2[key]) {
            return false;
        }
    }
    return true;
}
var checkInclusion = function(s1, s2) {
    if(s1.length > s2.length) return false;
    let s1Frequency = {};
    let windowFrequency = {};
    for (let char of s1) {
        s1Frequency[char] = (s1Frequency[char] || 0) + 1;
    }
    let begin = 0;
    let end = 0;
    while(end < s2.length + 1){
        if(end < s1.length) {
            windowFrequency[s2[end]] = (windowFrequency[s2[end]] || 0) + 1;
            end++
            continue;
        }
        if(objectsMatch(s1Frequency,windowFrequency)){
            return true;
        }

        windowFrequency[s2[begin]] = windowFrequency[s2[begin]]-1;
        windowFrequency[s2[end]] = (windowFrequency[s2[end]] || 0) + 1;
        begin++;
        end++;
    }
    return false
};

:::

<hr/>

### 東

:::spoiler Code

var checkInclusion = function(s1, s2) {
    if (s2.length < s1.length) {
        return false;
    }
    
    let requiredLength = s1.length;
    let map = new Map();
    for (let char of s1) {
        map.set(char, map.get(char) + 1 || 1);
    }
    
    let i = 0, j = 0;
    while (j < s2.length) {
        if (map.get(s2[j]) > 0) {
            requiredLength--;
        }
        map.set(s2[j], map.get(s2[j]) - 1);
        j++;
        if (requiredLength === 0) {
            return true;
        }
        if (j - i === s1.length) {
            if (map.get(s2[i]) >= 0) {
                requiredLength++;
            }
            map.set(s2[i], map.get(s2[i]) + 1);
            i++;
        }
    }
    return false;
};

:::

<hr/>

### Jessie

:::spoiler Code

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {

    let s1CharRecordArr = new Array(26).fill(0);
    let s2CharRecordArr = new Array(26).fill(0);

    //  Record s1
    for (let i = 0; i < s1.length; i++) {
        s1CharRecordArr[alphabetToNumber(s1[i])]++;
    }

    let tempStr = '';

    //  Check the difference between s1 and s2 records
    for (let i = 0; i < s2.length; i++) {

        let currentChar = s2[i];

        //  Remove first char from both record and temp
        if (tempStr.length >= s1.length) {

            let lpop = tempStr.substring(0, 1);
            s2CharRecordArr[alphabetToNumber(lpop)]--;

            tempStr = tempStr.substring(1);
        }

        //  Insert new char
        tempStr += currentChar;
        s2CharRecordArr[alphabetToNumber(currentChar)]++;

        //  No difference === BINGO!
        if (s1CharRecordArr.join() === s2CharRecordArr.join()) return true;

    }

    return false;

};

/**
 * Convert alphabet to numbers from 1 to 26
 * @param {string} char Alphabet a - z
 * @returns {number}
 */
function alphabetToNumber(char) {
    return char.charCodeAt(0) - 97;
}

:::

<hr/>

### 皮皮

:::spoiler Code

:::
<br>

## Live Coding

:::spoiler (name)

// write your code here

:::