sliding_window.md

Sliding Window

Fundamentally this is a two pointer approach

How it works:

• A general way is to use a hashmap assisted with two pointers.
• Use two pointers: start and end to represent a window.
• Move end to find a valid window.
• When a valid window is found, move start to find a smaller window.
• To check if a window is valid, we use a map to store (char, count) for chars in t, and use counter for the number of chars of t to be found in s.

There are two keys here:

1. the two pointers both start from the beginning of the second string initially
2. move j until j - i == len(first_string)

def sliding_window(nums):
    left = 0  # initiate the left boundary of window
    for right in range(len(nums)):  # iterate the right boundary of window
        while is_valid_window:
            left += 1  # Reduce left boundary to shrink window size

The template code is fairly simple.

Basically we iterate through the given list, and create a window.

When there the condition is satisfied (i.e. subset of the list satisfied the required returning condition), we reduce the left side to shrink the window, to find the best solution (most cases its the minimum subset of given list)

Reference:

• Leetcode 567 detailed explanation
• 10-line template that can solve most 'substring' problems
• Sliding Window algorithm template to solve all the Leetcode substring search problem.

Practice:

• 594. Longest Harmonious Subsequence
• 3. Longest Substring Without Repeating Characters
• 159. Longest Substring with At Most Two Distinct Characters
• 438. Find All Anagrams in a String
• 1156. Swap For Longest Repeated Character Substring
• 1004. Max Consecutive Ones III
• 76. Minimum Window Substring
• 30. Substring with Concatenation of All Words