Learning Journal

2/13/2024

Permutation in String - hashArr 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]++
    }

    if(match()) return true;

    let l = 0, r = s1.length - 1;

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

        hashArr2[s2.charCodeAt(l) - aCharCode]--;
        l++;

        if(match()) return true;
    }

    return false;

    function match():boolean {
        for(let i = 0; i < 26; i++) {
            if(hashArr1[i] !== hashArr2[i])
                return false;
        }

        return true;
    }
};
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]++
    }

    if(match()) return true;

    let l = 0, r = s1.length - 1;

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

        hashArr2[s2.charCodeAt(l) - aCharCode]--;
        l++;

        if(match()) return true;
    }

    return false;

    function match():boolean {
        for(let i = 0; i < 26; i++) {
            if(hashArr1[i] !== hashArr2[i])
                return false;
        }

        return true;
    }
};

THE PROBLEM

Some insights after the second attempt at solving this problem.

First, the essence of the sliding window technique is that there is an invariant that you need to know everything about that window at all time. If base on those information, you can not find the thing you're looking for or cannot conclude, you move it 1 step to the right. Now, you need to eliminate the leftmost element and add the right neighbor of the rightmost element of the window. Now you don't know everything, the invariant is broke and you need to fix that by adding the information of the newly added element and eliminate the information of the removed element. Then, you continue the loop.

Second, in the function match, how do you know that you need to stop the loop when the check is false, not true? Because, if it returns true, you are still not sure that the rest of the elements also return true, so you need to continue. Basically, if you check for validity, you need to check all the way to the end because if you stop early, you don't know whether or not the rest is valid. However, if you want to find something, you stop when you found it, no need to go further.

Revised by ChatGPT

After a second attempt at solving this problem, a few key insights have emerged regarding the sliding window technique and the implementation of the match function.

Firstly, the core principle of the sliding window technique is maintaining an invariant that encapsulates complete knowledge about the current window at all times. This invariant ensures that if the desired condition is not met based on the current information within the window, the window shifts one step to the right. This shift involves excluding the leftmost element and including the next element on the right of the window. At this point the invariant is momentarily broken because the information has changed with the exclusion and inclusion of the elements. The next step is to update the invariant by incorporating the information about the newly added element and removing the information about the excluded element, thus restoring the invariant and allowing the process to continue.

Secondly, the logic behind the match function is crucial for understanding when to terminate the loop. The function ceases when a mismatch (false) is encountered because a single mismatch invalidates the permutation condition. If the function returns true, it means the current window matches the target pattern, but it does not guarantee that the rest of the window will also match; this, the verification must continue through the entire window. In essence, when checking for a condition to be met (such as a permutation match), it is necessary to examine all elements to ensure validity. Conversely, if the objective is to identify the presence of a condition (such as finding a specific element), the search can terminate as soon as the condition is found.

This approach underscores the importance of thoroughly understanding the underlying logic of algorithmic techniques like the sliding window and the nuances of their implementation to solve specific problems effectively.