Technique Sliding Windows algorithms

Coding Problem: Given a string s and a character c, find the distance for all characters in the string to the character c in the string s. You can assume that the character c will appear at least once in the string. This problem was recently asked by Uber.

Example:

For example, given shortest_dist('helloworld', 'l') , you should return [2, 1, 0, 0, 1, 2, 2, 1, 0, 1].

Problem solution:

1) Technique: Sliding Windows (in this case two windows right and left)

Window start and end pointers:

The start and end pointers of the window allow us to go through the chain increasing or decreasing the size of the window itself = end -start, at the beginning the 'end' pointer is the only one that is increasing, the start pointer maintains the position until that the char appears on the scene. With the appearance of char, the pivot is updated, the size of the window and the distances between the pivot and the elements that formed the window up to that moment are updated.

Resize the windows:

We can resize the windows when we find an occurrence of the character in char = 'l'. The index 'end' of the window goes through the entire chain and the start maintains the position until we find a pivot = (char occurrences).

Pivot:

The pivot variables allow us to have a reference point for the last appearance of char = 'l' in the chain, with this pivot we calculate the distance between the end pointer and the last appearance of char.

Big O(N):

In short, I can say that this solution has an O (n * m) where 'n' is the length of 'st' and 'm' are the occurrences of the 'char'. So the inner loop is just to update the 'start' pointer and 'pivot', the more occurrences of the character, the more times this loop will run. Finally, O (n) is the best pattern to describe the behavior of these algorithms. We highlight the fact of using two windows to go through the chain, this reduces to a certain extent the size of the update cycles.

Code:

function shortestDist(st, char) {

    let len = st.length - 1
    let [
        winLeftStart,
        winLeftEnd,
        winRightStart,
        winRightEnd
    ] = [0, 0, len, len];
    let [pivotLeft, pivotRight] = [null, null];
    let dist = [];

    while (winLeftEnd <= len) {

        /** Window Left*/
        if (st[winLeftEnd] === char) {

            pivotLeft = winLeftEnd;
            while (winLeftStart <= pivotLeft) {
                dist[winLeftStart] = pivotLeft - winLeftStart;
                ++winLeftStart;

            }

        } if (!!pivotLeft) {

            if (dist[winLeftEnd]) {
                //End when have first match in dist
                dist[winLeftEnd] =
                    dist[winLeftEnd] < winLeftEnd - pivotLeft ?
                        dist[winLeftEnd] :
                        winLeftEnd - pivotLeft;
                return dist;
            }

            dist[winLeftEnd] = winLeftEnd - pivotLeft;
        }


        /** Window right*/
        if (st[winRightEnd] === char) {

            pivotRight = winRightEnd;
            while (winRightStart >= pivotRight) {

                dist[winRightStart] = winRightStart - pivotRight;
                --winRightStart;
            }

        } else if (!!pivotRight) {

            dist[winRightEnd] = pivotRight - winRightEnd;
        }

        /** Grow Windows*/
        --winRightEnd;
        ++winLeftEnd;
    }
 return [];
}

Simple test:

console.log(shortestDist('helloworld', 'l'))


//        h  e  l  l  o  w  o  r  l  d
// resp. [2, 1, 0, 0, 1, 2, 2, 1, 0, 1]
//        0  1  2  3  4  5  6  7  8  9

You can check

code by @difo23

Comments

[pentacular]

if (!!pivotLeft) { ... }

Just wondering if there's a special reason you're using this construct.

It looks seems entirely equivalent to

if (pivotLeft) { ... }

to me, so I'm wondering if I've overlooked something.

[Lizandro J. Ramírez]

I don't have a special condition to use (!!) it is just custom, I like that the conditions in a certain way handle Boolean only, so when (!! Null) it allows me to be aware of its boolean value although it does not affect the final solution.