Sliding Window

Reach for it when

• Longest / shortest contiguous subarray or substring with a property
• Property is monotonic: shrinking a valid window keeps it valid (or vice versa)
• Fixed-size window averages or counts

Core idea

Each element enters the window once (right pointer) and leaves once (left pointer), so the total work is O(n). Keep incremental state (counts, sum, distinct) so updates on enter/leave are O(1), and record the answer whenever the window is valid.

Template · O(n) time, O(k) space for k distinct keys

def longest_valid(s):
    count = {}
    best = l = 0
    for r, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1          # expand
        while not valid(count):                    # shrink until valid
            count[s[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

int longestValid(const string& s) {  // here: no repeated characters
    unordered_map<char, int> count;
    int best = 0, l = 0;
    for (int r = 0; r < (int)s.size(); r++) {
        count[s[r]]++;                       // expand
        while (count[s[r]] > 1) {            // shrink until valid
            count[s[l]]--;
            l++;
        }
        best = max(best, r - l + 1);
    }
    return best;
}

Common pitfalls

• Windows do not work with negative numbers for sum targets: use prefix sums
• Off-by-one in the window length (r - l + 1)
• For minimum windows, record the answer inside the shrink loop

Practice · 0 / 12 done

• Best Time to Buy and Sell StockEasy
• Find the Index of the First Occurrence in a StringEasy
• Maximum Average Subarray IEasy
• Design Hit CounterMedium
• Fruit Into BasketsMedium
• Longest Repeating Character ReplacementMedium
• Longest Substring Without Repeating CharactersMedium
• Maximum Coins From K Consecutive BagsMedium
• Permutation In StringMedium
• Subarray Product Less Than KMedium
• Minimum Window SubstringHard
• Sliding Window MaximumHard