Learning Journal

2/13/2024

Permutation in String - count approach - 2nd attempt

Tags: algorithms leetcode sliding_window

function checkInclusion(s1: string, s2: string): boolean {
    const hashArr1 = Array(26).fill(0);
    const hashArr2 = Array(26).fill(0);
    const aCharCode = "a".charCodeAt(0);

    for(let i = 0; i < s1.length; i++) {
        hashArr1[s1.charCodeAt(i) - aCharCode]++
        hashArr2[s2.charCodeAt(i) - aCharCode]++
    }

    let count = 0;
    for(let i = 0; i < 26; i++) {
        if(hashArr1[i] === hashArr2[i])
            count++;
    }

    if(count === 26) return true;
    
    let l = 0, r = s1.length - 1;

    while(r < s2.length - 1) {
        r++;
        const curIR = s2.charCodeAt(r) - aCharCode;
        hashArr2[curIR]++;

        if(hashArr1[curIR] === hashArr2[curIR])
            count++;
        else if (hashArr1[curIR] === hashArr2[curIR] - 1)   
            count--;

        const curIL = s2.charCodeAt(l) - aCharCode;
        hashArr2[curIL]--;

        if(hashArr1[curIL] === hashArr2[curIL])
            count++;
        else if (hashArr1[curIL] === hashArr2[curIL] + 1)   
            count--;

        if(count === 26) return true;

        l++;
    }

    return false;


};
function checkInclusion(s1: string, s2: string): boolean {
    const hashArr1 = Array(26).fill(0);
    const hashArr2 = Array(26).fill(0);
    const aCharCode = "a".charCodeAt(0);

    for(let i = 0; i < s1.length; i++) {
        hashArr1[s1.charCodeAt(i) - aCharCode]++
        hashArr2[s2.charCodeAt(i) - aCharCode]++
    }

    let count = 0;
    for(let i = 0; i < 26; i++) {
        if(hashArr1[i] === hashArr2[i])
            count++;
    }

    if(count === 26) return true;
    
    let l = 0, r = s1.length - 1;

    while(r < s2.length - 1) {
        r++;
        const curIR = s2.charCodeAt(r) - aCharCode;
        hashArr2[curIR]++;

        if(hashArr1[curIR] === hashArr2[curIR])
            count++;
        else if (hashArr1[curIR] === hashArr2[curIR] - 1)   
            count--;

        const curIL = s2.charCodeAt(l) - aCharCode;
        hashArr2[curIL]--;

        if(hashArr1[curIL] === hashArr2[curIL])
            count++;
        else if (hashArr1[curIL] === hashArr2[curIL] + 1)   
            count--;

        if(count === 26) return true;

        l++;
    }

    return false;


};

THE PROBLEM

I've made an improvement to the solution in this approach.

As I previously said, the core principle of the sliding window technique is to maintaining an invariant that encapsulates complete knowledge about the current window at all times. When we slide the window to the right, the invariant is broken, and thus, we need to update the information to fix it.

So, what is the complete knowledge in this case? The complete knowledge about the current window is whether or not the two hashArr match. So, if they match, all of their elements will be the same, which means, if we count the number of times that each pair of elements match, then, at the end, if the count is equal to 26, we know that they match (because there are 26 letters in the alphabet). So, another way to keep track of the complete knowledge of the window is just to maintain the count variable.

Revised by ChatGPT

I have refined the solution by optimizing the approach towards maintaining the invariant in the sliding window technique. As previously discussed, the essence of this technique lies in preserving a comprehensive understanding of the current window's state at all times. This understanding is momentarily disrupted when the window slides right, necessitating an update in our knowledge to restore the invariant.

In this specific problem, the "complete knowledge" pertains to the comparison between two hash arrays, which represent the frequency of each letter in the strings s1 and s2. If theses arrays match perfectly, it indicates that the current window in s2 is a permutation of s1. This condition can be efficiently monitored by maintaining a count of the elements that match between the two hash arrays. When this count equals 26, the total number of letters in the English alphabet, it signifies a complete match between the arrays, and thereby, a permutation of s1 within s2.

The innovative aspect of this approach is the utilization of the count variable to track the invariant. Rather than comparing the entire hash arrays each time the window slides, we adjust the count based on the specific changes at the window's borders. This method significantly streamlines the process of verifying the invariant, making the solution more efficient.