Summary of sliding window issues

Scope of application

1、Generally a string or a list
2、Generally it is required that the most value (maximum length, shortest length, etc.) or sub-sequence

algorithmic thinking

1. Use the left and right pointer trick of double pointers in a sequence, initialize left = right = 0, and call the index closure interval [left, right] a window.
2. First, keep increasing the right pointer to expand the window [left, right] until the sequence in the window meets the requirements.
3. At this point, stop adding right, and instead keep adding left pointers to shrink the window [left, right] until the sequence in the window no longer meets the requirements. At the same time, each time before increasing left, to update the results of a round.
4. Repeat steps 2 and 3 until right reaches the end of the sequence.
The idea is very simple: step 2 is equivalent to finding a feasible solution, and then step 3 is optimizing the feasible solution to find the optimal solution. The left and right pointers take turns moving forward, the window size increases and decreases, and the window keeps sliding to the right.

Note： Because each time right finds a new string it moves backward, pointing to the next character to be judged, so if you're judging the length of a string you should be using theright-left, not right-left+1.

code template

func slidingWindowTemplate(s string) int {
    left, right := 0, 0 // Initialize the left and right boundaries of the window.
    result := 0 // store the result
    window := make(map[byte]int) // record the frequency of elements in the window, or other window states

    // Iterate over arrays or strings
    for right < len(s) {
        // 1. Expand window, update window state
        charRight := s[right]
        window[charRight]++ // add character to window
        charRight := s[right] window[charRight]++ // Add character to window.

        // 2. Shrink the window if it doesn't fulfill the condition.
        for /* Condition: Window does not fulfill requirement */ {
            charLeft := s[left]
            window[charLeft]-- // move the left character out of the window
            left++
        }

        // 3. Update the result
        result = max(result, right - left) // For example, record the maximum length of the window
    }

    // 4. Return the final result
    return result
}

func max(a, b int) int { if a > b {
    if a > b {
        b { if a > b { return a
    b { return a}
    return a }
}