LeetCode Patterns Flashcards: Sliding Window, Fixed Size, Dynamic Size, Substring

The sliding window pattern maintains a window of elements that slides through an array or string, processing elements as they enter and leave the window. It solves problems involving contiguous subarrays or substrings, such as finding the maximum sum subarray of size k, the longest substring without repeating characters, or the smallest subarray with a sum greater than a target. The window is defined by left and right pointers. Fixed-size windows move both pointers together. Dynamic-size windows expand the right pointer and contract the left pointer based on a condition.

A fixed-size sliding window maintains exactly k elements. Start by computing the result for the first k elements. Then slide the window one position right by adding the new element entering from the right and removing the element leaving from the left, updating the result in O of one time per step. This avoids recomputing the entire window from scratch at each position. Total time is O of n. Use it when the problem specifies a fixed window size, such as "maximum average of subarray of length k" or "find all anagrams of a pattern in a string" where the window size equals the pattern length.

A dynamic-size sliding window expands and contracts based on a condition. Move the right pointer to expand the window until a condition is violated, then move the left pointer to shrink the window until the condition is restored. At each valid state, update the result. For example, to find the longest substring without repeating characters, expand right to include new characters. When a duplicate is found, shrink from the left until the duplicate is removed. The left pointer never moves backward, so both pointers traverse the array at most once each, giving O of n total time.

Use a dynamic sliding window with a hash set tracking characters in the current window. Expand the right pointer to add characters. When a character already exists in the set, shrink from the left, removing characters from the set, until the duplicate is gone. At each step, update the maximum length as right minus left plus one. A hash map storing the last index of each character offers a small optimization: when a duplicate is found, jump the left pointer directly past the previous occurrence instead of shrinking one character at a time. Both approaches run in O of n time.

Expand the right pointer until the window contains all characters from the target string, tracked by comparing character frequency maps. Once valid, try to shrink from the left while maintaining validity, updating the minimum valid window found. When shrinking makes the window invalid, resume expanding right. Use a counter tracking how many target characters are satisfied to determine validity in O of one rather than comparing full frequency maps each time. The overall time is O of n plus m where n is the source string length and m is the target length.

Look for these signals in the problem statement: the input is a linear data structure like an array or string, you need to find a contiguous subarray or substring, the problem asks for "longest," "shortest," "maximum," or "minimum" of something satisfying a condition, or there is a constraint on what the window can contain like "at most k distinct characters" or "sum at least target." If the problem asks about subsequences rather than subarrays, sliding window does not apply because subsequences are not contiguous. ---