Permutation in String

Look for permutation of s2 in s1 and return true or false

Problem Statement

Given two strings, s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if any rearrangement of s1's characters appears as a substring within s2.

Examples

Example 1

Input: s1 = "ab", s2 = "eidbaooo"

Output: true

Explanation: s2 contains a permutation of s1 — the substring "ba".

Example 2

Input: s1 = "ab", s2 = "eidboaoo"

Output: false

Constraints

• 1 ≤ s1.length, s2.length ≤ 10⁴ (this value appeared as "104" in the original text — it most likely means 10⁴, but you may want to double-check the original source)
• s1 and s2 only contain lowercase English letters.

Solution

We solve this using a sliding window of a fixed size (the length of s1). We slide this window across s2, and check if the characters inside the window exactly match what's needed to form a permutation of s1.

Steps

• First, we build a frequency map, requiredMap, counting how many times each character appears in s1.
• We track required, the number of unique characters we need to match, and current, how many of those characters are currently matched exactly in our window.
• We build the first window using the first s1.length characters of s2:
  • For each relevant character, we update our currentWindow map.
  • If a character's count in the window now exactly matches its required count, we increase current.
• If current already equals required after building this first window, we've found a match right away, so we return true.
• Otherwise, we slide the window forward, one character at a time, until we reach the end of s2:
  • We remove the character that just left the window (from the left side), and update our counts accordingly. If removing it broke an exact match, we decrease current.
  • We add the character that just entered the window (on the right side), and update our counts. If this creates a new exact match, we increase current.
  • After each slide, we check again if current equals required. If it does, we've found a valid permutation, so we return true.
• If we slide all the way through s2 without finding a match, we return false.

Code

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
    let currentWindow = new Map();

    let requiredMap = new Map();

    for (let i = 0; i < s1.length; i++) {
        requiredMap.set(s1[i], (requiredMap.get(s1[i]) ?? 0) + 1);
    }

    let required = requiredMap.size;
    let current = 0;

    for (let i = 0; i < s1.length; i++) {
        let curr = s2[i];

        if (requiredMap.has(curr)) {
            currentWindow.set(curr, (currentWindow.get(curr) ?? 0) + 1);

            if (currentWindow.get(curr) === requiredMap.get(curr)) {
                current++;
            }
        }
    }
    if (current === required) {
        return true;
    }

    for (let i = 1; i <= s2.length - s1.length; i++) {

        let last = s2[i - 1];
        let newChar = s2[i + s1.length - 1];

        if (requiredMap.has(last)) {

            if (currentWindow.get(last) === requiredMap.get(last)) {
                current--;
            }
            currentWindow.set(last, currentWindow.get(last) - 1);
        }

        if (requiredMap.has(newChar)) {
            currentWindow.set(newChar, (currentWindow.get(newChar) ?? 0) + 1);

            if (currentWindow.get(newChar) === requiredMap.get(newChar)) {
                current++;
            }
        }
        if (current === required) {
            return true;
        }
    }

    return false;
};