Sliding window

A window that grows on the right and shrinks from the left whenever a condition breaks.

Trigger in the prompt: 'Contiguous subarray or substring' plus 'longest' or 'shortest'.

easyBest Time to Buy and Sell Stock

Find the maximum profit from one buy and one later sell.

Trigger

'Buy once, sell once', 'maximum difference with order'.

Approach
  1. Single pass: track the minimum seen so far and the best profit against it.
  2. It is a degenerate sliding window, or Kadane on the differences — either framing is fine.
  3. If no profit is possible, return zero.
Target complexity

O(n) time, O(1) space.

Pitfall

Sorting. It destroys the ordering constraint that the buy must precede the sell.

Say it out loud

“One pass tracking the minimum price so far and the best profit against it. Sorting would be tempting and completely wrong, because the buy has to come before the sell — the ordering is the constraint.”

Solve on LeetCode
mediumLongest Repeating Char Replacement

Find the longest substring achievable by replacing at most k characters.

Trigger

'At most k changes', 'longest valid window'.

Approach
  1. Window validity: window length − count of the most frequent character <= k.
  2. Keep a frequency map and the running maximum frequency.
  3. The subtlety: you never need to decrease the max frequency. The window only grows when a new maximum is found, so a stale max cannot produce a wrong answer.
Target complexity

O(n) time, O(alphabet) space.

Pitfall

Recomputing the maximum frequency on every shrink. It is unnecessary and turns the pass into O(26n).

Say it out loud

“The window is valid when its length minus the most frequent character's count is at most k. The clever part is that I never have to decrease the running max frequency — the window only expands when a genuine new maximum appears, so a stale value can't produce a larger wrong answer.”

Solve on LeetCode
mediumLongest Substring Without Repeating Chars

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

Trigger

'Longest substring' plus a validity condition — the sliding window signature.

Approach
  1. Window with two pointers; a map from character to its last index.
  2. On a repeat inside the window, jump the left pointer past the previous occurrence.
  3. Take the max of left and previous+1 — the previous occurrence may be behind the window already.
Target complexity

O(n) time, O(min(n, alphabet)) space.

Pitfall

Moving the left pointer backwards. Guard with a max, or the window becomes invalid.

Say it out loud

“Classic sliding window. I keep the last index of each character, and on a repeat I jump the left edge past it — but only forwards, so I take a max, because that occurrence may already be outside the window.”

Solve on LeetCode
mediumPermutation in String

Decide whether one string contains any permutation of another as a substring.

Trigger

'Contains a permutation' — a fixed-size sliding window.

Approach
  1. The window has a **fixed** size, len(t) — that is what distinguishes it from the variable window problems.
  2. Keep two frequency counts and slide: add the entering character, remove the leaving one.
  3. Compare counts in O(26) per step, or maintain a `matches` counter for O(1).
Target complexity

O(n) time, O(alphabet) space.

Pitfall

Rebuilding the counter for each window. That is O(n·m) and defeats the sliding.

Say it out loud

“Because the window size is fixed, this is a slide rather than a grow-and-shrink: one character in, one out, per step. I keep a count of how many letters currently match their target so the comparison is constant rather than a full dictionary compare.”

Solve on LeetCode
hardMinimum Window Substring

Find the shortest substring of s containing every character of t, with multiplicity.

Trigger

'Smallest window containing all of…' — the canonical hard sliding window.

Approach
  1. Two maps: what is needed, and what the window currently has.
  2. A `formed` counter of how many distinct required characters are fully satisfied — that avoids comparing maps on every step.
  3. Expand right until valid, then contract left while it stays valid, recording the best.
  4. Multiplicity matters: t may contain repeats.
Target complexity

O(n + m) time, O(alphabet) space.

Pitfall

Comparing the two frequency maps at every step. That is O(26) per position and misses the point of the counter.

Say it out loud

“Two frequency maps plus a counter of how many required characters are currently satisfied. That counter is what keeps it linear — otherwise I'd be comparing dictionaries at every position. Expand until valid, then contract while still valid, recording the shortest.”

Solve on LeetCode
hardSliding Window Maximum

Return the maximum of every window of size k as it slides across the array.

Trigger

'Maximum in each window' — this is a monotonic deque, not a plain sliding window.

Approach
  1. A heap gives O(n log k) and is a fine first answer.
  2. The linear answer is a monotonic decreasing deque of **indices**.
  3. Before appending, pop from the back everything smaller than the incoming value — they can never be the max again.
  4. Pop from the front anything that has fallen out of the window. The front is always the answer.
Target complexity

O(n) time, O(k) space.

Pitfall

Storing values instead of indices in the deque. Then you cannot tell when an element has left the window.

Say it out loud

“A heap is n log k. Linear needs a monotonic deque holding indices — indices, not values, so I can tell when something falls out of the window. Anything smaller than the incoming element can never be the maximum again, so I discard it, and the front of the deque is always the answer.”

Solve on LeetCode