Sliding Window

Step 1 Understand it

Remember it by

Grow the right edge; while the window breaks the rule, shrink the left edge.

Watch it happen

The idea

A window is a contiguous slice [left, right]. You extend it to the right one step at a time, and whenever it stops being valid you move the left edge forward until it's valid again. Each item enters and leaves the window at most once, so it's O(n).

Picture it

flowchart LR
  A["move right one step:<br/>add the new item"] --> Q{"window breaks<br/>the rule?"}
  Q -->|"yes"| S["remove the left item,<br/>move left one step"] --> Q
  Q -->|"no"| U["update the best answer"] --> A

Analogy

Reading a long sentence through a cardboard slot you can stretch. You widen it to see more words; when it shows something you're not allowed (a repeated letter), you slide the left edge until it's gone.

Where the analogy breaks

A cardboard slot can jump anywhere. The window can't: both edges only ever move right, which is exactly what makes it O(n).

Step 2 Recognise it

Words that signal it

• 'Contiguous subarray' or 'substring'
• 'Longest / shortest / maximum … such that …'
• 'At most k', 'without repeating', 'containing all of'
• A fixed size: 'every window of size k'

Don't confuse it with

• Two Pointers: Both use left and right. Sliding window keeps everything between them (a contiguous range) and both move the same way.
• Prefix Sum + Hash Map: 'Subarray sum equals k' with negative numbers: shrinking the window doesn't reliably reduce the sum, so the window breaks — use prefix sums.

Gut check

Contiguous range, and I want the best one that obeys a rule? → sliding window.

How to recognise it in an interview

The prompt explicitly uses the words 'contiguous', 'substring', 'subarray', or 'window'.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

def solve(s):
    left = 0
    state = ...                         # what's inside the window (set, counts, sum)
    best = 0
    for right in range(len(s)):
        # 1. add s[right] to the window
        while ...:                      # 2. while the window breaks the rule
            # remove s[left] from the window
            left += 1
        best = max(best, right - left + 1)   # 3. window is valid: record it
    return best

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> window = new HashSet<>();
        int left = 0, maxLength = 0;
        for (int right = 0; right < s.length(); right++) {
            while (window.contains(s.charAt(right))) {
                window.remove(s.charAt(left));
                left++;
            }
            window.add(s.charAt(right));
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

Common mistakes

• Using if instead of while to shrink: one step may not be enough to make the window valid again.
• Updating the best answer before the window is valid.
• Window length is right − left + 1, not right − left.
• Growing the right pointer before shrinking the left pointer correctly.
• Using O(N^2) nested loops when a sliding window makes it beautiful O(N).

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

def max_profit(prices):
    left, best = 0, 0                  # left = cheapest day so far
    for right in range(1, len(prices)):
        if prices[right] < prices[left]:
            left = right
        else:
            best = max(best, prices[right] - prices[left])
    return best

def length_of_longest_substring(s):
    seen = set()
    left = best = 0
    for right, ch in enumerate(s):
        while ch in seen:              # shrink until ch is no longer repeated
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

Step 5 Practise

Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.

Easy

1. Mark "Best Time to Buy And Sell Stock" as solved Best Time to Buy And Sell Stock Easy

   Pick one day to buy and a later day to sell for the biggest profit.

   Show answer

   Technique: Sliding window (track the minimum)

   The clue: Buy before sell, best difference across the array.

   The trick: Keep the cheapest price so far as the left edge; profit = today − cheapest.

Medium

1. Mark "Longest Substring Without Repeating Characters" as solved Longest Substring Without Repeating Characters Medium

   Find the length of the longest substring with no repeated characters.

   Show answer

   Technique: Variable sliding window + set

   The clue: 'Longest substring such that …' = contiguous range with a rule.

   The trick: Expand right; while the new character is already in the window, remove from the left.

2. Mark "Longest Repeating Character Replacement" as solved Longest Repeating Character Replacement Medium

   With at most k letter changes, find the longest substring of one repeated letter.

   Show answer

   Technique: Sliding window + counts

   The clue: 'Longest substring' with 'at most k' changes.

   The trick: A window is valid while (window length − count of its most common letter) ≤ k; shrink when it's not.

3. Mark "Permutation In String" as solved Permutation In String Medium

   Decide whether some rearrangement of string s1 appears as a substring of s2.

   Show answer

   Technique: Fixed-size sliding window + counts

   The clue: A rearrangement has the same length and the same letter counts.

   The trick: Slide a window of length len(s1) over s2, updating letter counts, and compare with s1's counts.

Hard

1. Mark "Minimum Window Substring" as solved Minimum Window Substring Hard

   Find the shortest substring of s containing every character of t (with counts).

   Show answer

   Technique: Variable sliding window + 'have / need' counts

   The clue: 'Shortest substring containing all of …'.

   The trick: Expand until all needed counts are met, then shrink from the left while still valid, recording the shortest.

2. Mark "Sliding Window Maximum" as solved Sliding Window Maximum Hard

   Return the maximum of every window of size k.

   Show answer

   Technique: Sliding window + monotonic deque

   The clue: Fixed window size, and you need the max each time.

   The trick: Keep a deque of indexes with decreasing values; drop the front when it leaves the window — the front is the max.

What to say in the interview

'Since we need a contiguous subarray, we can maintain a sliding window to keep our time complexity strictly linear.'

Follow-up prep

Can you do this if the array has negative numbers? (Hint: usually sliding window fails for sums with negatives, use prefix arrays instead).