Permutation in String medium

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 and only if some permutation of s1 is a substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo" Output: true Explanation: s2 contains the permutation "ba" of s1 which is a substring of s2.

Example 2:

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

Steps:

1. Frequency Mapping: Create a frequency map (using an object or a map) for s1 to store the count of each character.

2. Sliding Window: Use a sliding window of the same size as s1 to traverse s2. Maintain a frequency map for the characters within the current window.

3. Comparison: Compare the frequency map of the window with the frequency map of s1. If they are identical, it means the window contains a permutation of s1.

4. Sliding: Slide the window one character at a time by adding the new character's frequency and removing the old character's frequency.

5. Return: If a match is found at any point, return true. Otherwise, return false after traversing the entire s2.

Explanation:

The solution leverages the concept of a sliding window and frequency counting. We don't need to generate all permutations of s1; instead, we check if the character frequencies within a sliding window in s2 match the frequencies in s1. This significantly improves efficiency compared to brute-force methods.

Code (Typescript):

function checkInclusion(s1: string, s2: string): boolean {
    if (s1.length > s2.length) return false;

    const s1Map: { [key: string]: number } = {};
    for (let char of s1) {
        s1Map[char] = (s1Map[char] || 0) + 1;
    }

    let windowStart = 0;
    let windowEnd = 0;
    const windowMap: { [key: string]: number } = {};

    while (windowEnd < s2.length) {
        const char = s2[windowEnd];
        windowMap[char] = (windowMap[char] || 0) + 1;
        
        if (windowEnd - windowStart + 1 === s1.length) {
            if (areMapsEqual(s1Map, windowMap)) return true;
            const leftChar = s2[windowStart];
            windowMap[leftChar]--;
            if (windowMap[leftChar] === 0) delete windowMap[leftChar];
            windowStart++;
        }
        windowEnd++;
    }

    return false;
};


function areMapsEqual(map1: { [key: string]: number }, map2: { [key: string]: number }): boolean {
    for (let key in map1) {
        if (map1[key] !== map2[key]) return false;
    }
    for (let key in map2) {
        if (map1[key] !== map2[key]) return false;
    }
    return true;
}

Complexity:

• Time Complexity: O(m + n), where n is the length of s2 and m is the length of s1. We traverse s2 once and the operations within the loop are O(1) on average.

• Space Complexity: O(m), to store the frequency maps. In the worst case, s1 contains unique characters.