Sliding window related algorithm questions

Xu Jiao April 21, 2021

First, sliding window related concepts

1.1 concept

Sliding window algorithm can be used to solve the subelement problem of array/string. It can transform the nested loop problem into a single loop problem and reduce the time complexity.

1.1 Features of Application Scenarios

The results that need to be output or compared are sequentially arranged in the original data structure
Every time the window slides, you only need to observe the changes of the elements at both ends of the window. No matter how long the window is, you only need to operate two elements at the beginning and end of the window. When the window is long, the number of operations can be significantly reduced
The integrity of the elements in the window is relatively strong. The window sliding can be realized only by manipulating the changes of the top and bottom positions, but all the elements in the window are often used when comparing the results

Two, sliding window solution ideas

2.1 Common algorithms that need to use sliding Windows

Longest string without repeating characters: Given a string, find the length of the longest string without repeating characters
Minimum length subarray: Given an array of n positive integers and a positive integer target. Find the smallest contiguous subarray [numsl, numSL +1,…, numsr-1, numsr] that satisfies the sum and ≥ target, and return its length. If no subarray exists, return 0
Sliding window maximum: Given an integer array nums, there is a sliding window of size K that moves from the leftmost of the array to the rightmost of the array. You can only see k numbers in the sliding window. The sliding window moves only one bit to the right at a time.

Returns the maximum value in the sliding window.
Minimum overwritten substring: gives you a string S and a string T. Returns the smallest string in S that covers all characters of t. Returns an empty string ” if no substring covering all characters of t exists in S.

2.2 Steps to solve the problem

Initialize the left and right Pointers of the sliding window: in solving the minimum covering substring, left = 0; right = t.length
Boundary condition judgment, exception processing: s.lenght < T. Length processing in solving the minimum covering substring;
General need to loop, determine the conditions out of the loop: minimum coverage substring solution in the right pointer is greater than the string, array length right > s.length, out of the loop
Determine the conditions for window pointer movement:
- In what scenario does the left pointer move: in solving the minimum covering substring, when the sliding window contains substring T, the left pointer moves
- In what scenario does the right pointer move: in solving the minimum covering substring, the sliding window does not contain substring T, and the right pointer moves

Three, sliding window often used knowledge points

3.1 How can I Determine if String A contains String B

First, a.length >= B. Length
After sorting: violence judgment, basic timeout
- sortA = a.split(”).sort().join(”)
- sortB = b.split(”).sort().join(”);
- sortA.indexOf(sortB) > -1
Use objects: Improve search efficiency
- Process a, B strings into {character: number}
- All characters in B exist in A, and the number of characters in B <= the number of characters in a string
Use a Map object in JavaScript
- Map.prototype.size: Returns the number of objects in the Map object
- Map.prototype.set(value) : Add an element
- Map.prototype.get(value): Gets an element
- Map.prototype.has(value): Whether there is an element
- Map.prototype.keys(): Returns a referenced Iterator. It contains the keys that are inserted sequentially for each element in the Map object
- Map.prototype.values(): Returns a referenced Iterator. It contains values that are inserted in order for each element in the Map object

3.2 How can I find the maximum and minimum values in an array

After sorting: violence to solve, basic timeout
- const sortA = a.sort((x, y) => x – y);
- Maximum value: sortA[A.length-1]
- Minimum value: sortA[0]
Using the Math method
- Max: math.max. Apply (null, a);
- Math.min.apply(null, a);
- ES6 methods: math.max (… a);

Four, common sliding window – the most small string solution

Description: 4.1

I give you a string s and a string T. Returns the smallest string in S that covers all characters of t. Returns an empty string ” if no substring covering all characters of t exists in S.

4.2 the sample:

Enter: s ="ADOBECODEBANC", t = "ABC"Output:"BANC"Enter: s ="a", t = "a"Output:"a"  
Copy the code

4.3 Schematic Steps:

Initialization phase: s = “ADBECOEBAC” t = “ABC”
- Initialize window left and right Pointers: left = 0; right = 2(t.length – 1)
- Initialize minimum string: minLength = “ADBECOEBACABC”; (s + t)
Round 1: window string ADB contains ABC; Not included: right pointer moves to the right;
Round 2: whether the window string ADBE contains ABC; Not included: The right pointer moves to the right
Round 3: whether the window string ADBEC contains ABC; Contains:
- MinStr = “ADBECOEBACABC “; minStr = “ADBEC”;
- Left pointer moves right
The fourth round of judgment: window string DBEC contains ABC, does not include: right pointer moves right
Round 5: whether the window string DBECO contains ABC, does not include: right pointer moves right
Round 6: the window string DBECOE contains ABC, does not include: right pointer moves right
The seventh round of judgment: whether the window string DBECOEB contains ABC, does not include: right pointer moves right
Round 8: whether window string DBECOEBA contains ABC; Contains:
- MinStr = “ADBEC”; minStr = “ADBEC”; minStr = “ADBEC”;
- Left pointer moves right
Round 9: window string BECOEBA contains ABC; Contains:
- MinStr = “ADBEC”; minStr = “ADBEC”;
- Left pointer moves right
Round 10: whether the window string ECOEBA contains ABC; Contains:
- MinStr = “ADBEC”; minStr = “ADBEC”;
- Left pointer moves right
Round 11: whether window string COEBA contains ABC; Contains:
- MinStr = “ADBEC”; minStr = “ADBEC”;
- Left pointer moves right
Round 12: whether the window string OEBA contains ABC; Not included: The right pointer moves to the right
Round 13: whether the window string OEBAC contains ABC; Contains:
- MinStr takes the minimum length of the initial value “ADBEC” and the current window string “OEBAC”, that is, minStr = “ADBEC”;
- Left pointer moves right
Round 14: whether the window string EBAC contains ABC; Contains:
- MinStr = “EBAC”; minStr = “EBAC”; minStr = “EBAC”; minStr = “EBAC”;
- Left pointer moves right
Round 15: whether window string BAC contains ABC; Contains:
- MinStr takes the minimum length of the initial value “ADBEC” and the current window string “BAC”, that is, minStr = “BAC”;
- Left pointer moves right
Round 16 judgment: Right pointer reaches the maximum value s.length-1; The window string AC is shorter than the comparison string ABC, breaking out of the loop
- Return final result minStr = “BAC”

4.4 Points needing attention in solving the problem: How to judge that window string A contains string B to be compared;

Use indexOf to sort the string/** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** *
const isInclude = (a, b) = > {
    const sortA = a.split(' ').sort((x, y) = > x -y).join(' ');
    const sortB = b.split(' ').sort((x, y) = > x -y).join(' ');
    return sortA.indexOf(sortB) > -1; }; ## Method 2: UseMapMethod to count whether a contains the number of characters in B. The same character in A should be greater than or equal to B [Object object in JavaScript can also be used directly]. The object access efficiency is highfunction createMap (b) {
    const map = new Map(a); [...b].forEach(res= > {
        map.has(res) ? map[res]++ : map(res) = 1;
    });
    return map;
}

function isContainerStr(a, b) {
    const mapA = createMap(a);
    const mapB = createMap(b);
    const keys = mapB.keys(); 
}
Copy the code

4.5 implementation

function createMap (b) {
    const map = new Map(a); [...b].forEach(res= > {
        const value = map.has(res) ? map.get(res) + 1 : 1;
        map.set(res, value);
    });
    return map;
}
function isContainedStr(mapA, mapB) {
    let isContainer;
    mapB.forEach((value, key) = > {
        if(! mapA.has(key) || mapA.get(key) < value) { isContainer =false; }});return isContainer === undefined;
}
function minWindow (s, t) {
    const tLength = t.length;
    const sLength = s.length;
    const con = s + t;
    if (sLength < tLength) {return ' '; }// Initialize the left and right Pointers of the sliding window
    let left = 0;
    let right = tLength;
    let minStr = con;
    const tObj = createMap(t);
    while (right <= sLength) {
        const subStr = s.substring(left, right);
        const subObj = createMap(subStr);
        const isContainer = isContainedStr(subObj, tObj);
        // contains the substring t
        if (isContainer) {
            minStr = subStr.length < minStr.length ? subStr : minStr;
            left++;
        } else{ right++; }}return minStr === con ? ' ' : minStr;
};
Copy the code

4.6 The above solution times out, so find the optimization point:

S = ADBECOEBAC including t = ABC the latest small string is the last BAC, which has the following characteristics: continuous, we do not need to record the middle string value, we only need to record the left pointer, and the minimum string length minLen. MinStr = s.substr(left, minLen);
IsContainedStr can’t get out of the loop with forEach. In fact, it only needs one key to stop the loop and get out.
Maintains an object(subObj) during the loop s string loop, adding characters on right++ or increasing the number of characters by 1, removing characters on left++ or decreasing the number of characters by 1.

4.7 Optimization implementation

function minWindow (s, t) {
    // The character object generated by the window string
    let subObj = {};
    ObjT = {A: 1, B: 1, C: 1} objT = {A: 1, B: 1, C: 1}
    let objT = {};
    [...t].forEach(char= > objT[char] ? objT[char]++ : objT[char] = 1);
    
    // Initialize the left and right Pointers of the window, because the window object subObj needs to be generated in the loop, so the right loop should start from 0
    let left = 0;
    let right = 0; 
    
    // Initializes the minimum string length (default infinity)
    let minLen = Infinity;
    
    // Initializes the starting point of the smallest string
    let start = -1; 
    
    let keyLen = Object.keys(objT).length;
    // Record the number of characters in the window string that match the number of characters in objT. If the number is the same as in keyLen, we assume that the current window string contains t
    let count = 0;
    
    while (right < s.length) {
        // The character to which the right pointer is currently pointing
        let char = s[right++];
        // The window string object is maintained in the loop, without the need to repeat the comparison internally
        subObj[char] ? subObj[char]++ : subObj[char] = 1;

        /** if the characters in t are all found in the window object in equal numbers during the loop. * We remember the start value at this time, because left will change later ** then the window string: minStr = s.substring(left, right) contains us t **/
        if(subObj[char] === objT[char]) {count++; }while(count === keyLen) {    
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            // The left pointer moves to the right
            let c2 = s[left++];
            if(subObj[c2]-- === objT[c2]) {count--; }}}return start === -1 ? ' ' : s.substr(start, minLen)
};
Copy the code