Permutation in String

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 one of s1’s permutations is the substring of s2.

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

Approach: Sliding Window

Since we are looking for a permutation of s1 inside s2, any valid permutation must be a contiguous substring of exactly length s1.length. This suggests a fixed-size sliding window approach.

We can compare the character frequencies of s1 and our current window in s2. Since the strings only contain lowercase English letters, we can use two arrays of size 26 to keep track of the character counts.

1. If the length of s1 is greater than s2, return false immediately.
2. Initialize two arrays s1Count and s2Count of size 26 to store the frequencies.
3. Count the character frequencies of s1 and the first s1.length characters of s2.
4. Initialize a variable matches to keep track of how many characters have the exact same frequency in both arrays. This allows us to compare the windows in $O(1)$ time.
5. Slide the window one character at a time from index s1.length to the end of s2:
   • If matches == 26, we found a permutation, so return true.
   • Add the new character entering the window (at right) by updating its count in s2Count and adjusting matches.
   • Remove the old character leaving the window (at left) by updating its count in s2Count and adjusting matches.
6. After the loop, do one final check if matches == 26. If so, return true.
7. If no match is found, return false.

Solution

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
function checkInclusion(s1, s2) {
    if (s1.length > s2.length) return false;

    const s1Count = new Array(26).fill(0);
    const s2Count = new Array(26).fill(0);

    for (let i = 0; i < s1.length; i++) {
        s1Count[s1.charCodeAt(i) - 97]++;
        s2Count[s2.charCodeAt(i) - 97]++;
    }

    let matches = 0;
    for (let i = 0; i < 26; i++) {
        if (s1Count[i] === s2Count[i]) {
            matches++;
        }
    }

    let left = 0;
    for (let right = s1.length; right < s2.length; right++) {
        if (matches === 26) return true;

        // Add right character to the window
        let index = s2.charCodeAt(right) - 97;
        s2Count[index]++;
        if (s1Count[index] === s2Count[index]) {
            matches++;
        } else if (s1Count[index] + 1 === s2Count[index]) {
            matches--;
        }

        // Remove left character from the window
        index = s2.charCodeAt(left) - 97;
        s2Count[index]--;
        if (s1Count[index] === s2Count[index]) {
            matches++;
        } else if (s1Count[index] - 1 === s2Count[index]) {
            matches--;
        }
        left++;
    }

    return matches === 26;
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the length of s2. We iterate through s2 with a sliding window. Updating the window counts and matches takes $O(1)$ time per character, making the window sliding process highly efficient.
• Space Complexity: $O(1)$ since we are using fixed-size arrays of length 26 to store character frequencies, regardless of the input string sizes.