cf.completefrontend
SLIDING WINDOW · CORE

Sliding window with a frequency map

Keep a map of how many times each value appears inside a sliding window, updating it as items enter and leave, to answer questions about the window's contents.

Time O(n)Space O(k)11 practice problemsStep-through picture

The idea

Some window questions are about what the window contains, not its total: no letter repeats, at most two kinds of items, every letter of a word appears. To answer them quickly, keep a frequency map: a Map from each value to how many times it appears inside the window right now.

When an item enters on the right, add one to its count. When an item leaves on the left, take one away, and delete the key when its count reaches zero. Then counts.size is the number of different values in the window, and counts.get(x) tells you how many copies of x it holds.

Combined with a growing and shrinking window, this answers questions like "the longest part of a string with at most k different characters" in one pass, without recounting the window each time.

An everyday example

A tally sheet at a museum door

A guard keeps a tally of how many visitors from each school are inside one small room. When a visitor walks in, the guard adds a mark next to their school. When one walks out, the guard rubs out a mark, and crosses the school off the sheet when its last visitor leaves. At any moment, the guard knows how many different schools are inside just by counting the names on the sheet.

How the example maps to the code
In the exampleIn the code
The roomThe window s[left..right]
The tally sheetcounts, a Map
A visitor walks incounts.set(ch, (counts.get(ch) ?? 0) + 1)
A visitor walks outcounts.set(out, counts.get(out) - 1)
Crossing a school off the sheetcounts.delete(out)
How many schools are insidecounts.size

From the slow way to sliding window with a frequency map

  1. Start with the obvious way: for each start left, extend the end one character at a time, put each character into a fresh Set, and stop when the set has more than k letters. Each start can scan most of the string, so this is O(n^2), and every start rebuilds the set from nothing.
  2. Sliding the window would avoid the rebuilds, but a Set can't handle a character leaving. If "p" leaves the window, is there another "p" still inside? A set only knows yes or no, not how many, so you can't tell whether to delete it.
  3. So count instead. A Map from each character to how many copies are in the window answers that question: when a character leaves, take one from its count, and delete the key only when the count reaches zero. Then counts.size is always the number of different characters in the window.
  4. With that, the window can grow and shrink like any variable window: add s[right], and while counts.size > k, remove s[left] and move left forward. Then measure. That loop is the sliding window with a frequency map.

How it works

  1. Create an empty counts map and set left = 0 and best = 0.
  2. Move right across the string. Add one to the count of s[right].
  3. While the window breaks the rule (here, counts.size > k), remove s[left]: take one from its count, delete the key at zero, and move left right.
  4. The window left..right now follows the rule. Compare its size, right - left + 1, with best.
  5. After the loop, return best.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function longestWithKDistinct(s, k) {
  2. const counts = new Map();
  3. let left = 0;
  4. let best = 0;
  5. for (let right = 0; right < s.length; right++) {
  6. const ch = s[right];
  7. counts.set(ch, (counts.get(ch) ?? 0) + 1);
  8. while (counts.size > k) {
  9. const out = s[left];
  10. counts.set(out, counts.get(out) - 1);
  11. if (counts.get(out) === 0) counts.delete(out);
  12. left++;
  13. }
  14. best = Math.max(best, right - left + 1);
  15. }
  16. return best;
  17. }

How fast it is

TimeO(n)
Extra memoryO(k)

Each character enters and leaves the window at most once, and each map update is constant time on average. The map holds at most k + 1 keys at any moment.

  • Best caseO(n)

    The whole string has at most k different letters, like "aaaa" with k = 1: left never moves, one map update per character.

  • Average caseO(n)

    Any string: each character enters the map once and leaves at most once, and each Map update is constant time on average.

  • Worst caseO(n)

    Letters change constantly, like "abcabc" with k = 1: almost every character is removed right after it's added. Still at most 2n updates.

Common mistakes

  • Leaving keys with a count of 0 in the map, so counts.size is too big and the window shrinks more than it should.
  • Using a plain object and Object.keys(counts).length inside the loop. Building the key list each time is O(k) per step; a Map with size is constant time.
  • Comparing two whole maps on every slide for anagram questions. It works but costs O(alphabet) each step; track a matched counter instead.
  • Forgetting that s[left] must be read before left++. Moving first removes the wrong character.

When to use it

Look for these clues in a problem:

  • The question is about a substring or subarray and talks about distinct values, repeats, or how many of each kind.
  • It says "at most k different", "no repeating", "contains all the letters of", or "a rearrangement of".
  • You need counts per value inside the window, not just a total.
  • The alphabet is small (letters) or values can be keys in a Map.

Check yourself

Answer each one in your head first, then open it.

Why can't a Set replace the map?

When a character leaves, a Set can't tell whether another copy is still in the window. Counts can: delete the key only when its count reaches 0.

What goes wrong if you don't delete keys whose count reaches 0?

counts.size keeps counting letters that are no longer in the window, so the window looks like it breaks the rule and shrinks more than it should.

In the trace, why did adding r at right = 5 remove 4 characters?

The window had three ps and two qs. counts.size only drops when one letter's count reaches 0, and the last p was at index 3, so left had to pass indexes 0 to 3.

At most how many keys can counts hold at once?

k + 1. Adding one character can push the size to k + 1, and the while loop brings it back to k before the next character is added.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 11 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps two promises. First, counts holds exactly the characters of s[left..right], each with its number of copies, and no key has a count of 0. Adding one at right and taking one away at left, deleting keys that reach 0, keeps this true at every step. So counts.size is always the number of different characters in the window.

Second, after the while loop, left is the smallest start whose window up to right has at most k different characters. This works because removing characters from the left can never add a new letter, so if a window has too many letters, every bigger window containing it does too. A start skipped for one right stays too early for every later right.

So for each right, left..right is the longest valid window ending there, and best keeps the largest of them. Every valid window ends somewhere, so best is the answer. Each character is added once and removed at most once, so the loop finishes after at most 2n map updates.

Going deeper

3 more ideas

Why deleting zero counts matters

counts.size counts keys, not copies. If a character's count drops to 0 and you leave the key in the map, counts.size still counts it as inside the window, and the window looks like it has more distinct characters than it does. Deleting the key at zero keeps counts.size equal to the number of different characters in the window.

Why it takes O(n) time

Each character is added to the map once, when right reaches it, and removed at most once, when left passes it. Each map update takes constant time on average. The map holds at most one key per distinct character in the window, so memory is O(k), or the alphabet size.

Fixed-size windows with a frequency map

To find every place where a rearrangement of a word appears, slide a window of the word's length and compare its counts with the word's counts. Instead of comparing the whole map each step, keep a number matched of letters whose counts agree, and update it only for the letter that enters and the letter that leaves.

Work it by hand

Every step in a table, with why

Find the longest part with at most 2 different letters. One step has to remove four characters, and only the last removal deletes a key.

s = "ppqpqrrqr", k = 2

SteprightchRemovedleftcountsbestWhy
10p-0{p: 1}1The first character enters. One letter, window size 1.
21p-0{p: 2}2A second p: the count goes up, but counts.size stays 1.
32q-0{p: 2, q: 1}3Two different letters, which is allowed.
43p-0{p: 3, q: 1}4Still two letters. The window is "ppqp".
54q-0{p: 3, q: 2}5Window "ppqpq", size 5, the best so far.
65rp, p, q, p4{q: 1, r: 1}5r makes 3 letters. Removing p (2 left), p (1 left), and q (1 left) doesn't help; the 4th removal takes the last p, its count hits 0, the key is deleted, and counts.size is 2.
76r-4{q: 1, r: 2}5Window "qrr", size 3.
87q-4{q: 2, r: 2}5Window "qrrq", size 4.
98r-4{q: 2, r: 3}5Window "qrrqr", size 5, which ties best.

It returns 5. Both "ppqpq" and "qrrqr" have 5 characters and 2 letters. The loop ends when right passes the last index.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Sliding window with a frequency mapO(n)O(k)The rule is about which values are in a contiguous run, such as distinct letters, repeats, or matching counts.
Every start with a fresh SetO(n^2)O(k)The string is short, or you want a simple reference version to test against.
Frequency map as an array of 26 countsO(n)O(1)The input is only lowercase English letters. Index with ch.charCodeAt(0) - 97, and track the number of non-zero counts yourself instead of counts.size.

Extra memory: O(k): the map holds at most k + 1 keys, and only for an instant before the shrink step. For letters only, that's at most the alphabet size.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Sliding window with a frequency map and the other approaches, on a scale where each line up is 10 times more steps.
  • Sliding window with a frequency map, Frequency map as an array of 26 counts O(n)
  • Every start with a fresh Set O(n^2)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Sliding window with a frequency map101,0001 million
Every start with a fresh Set1001 million1 trillion
Frequency map as an array of 26 counts101,0001 million

Inputs that need care

5 tricky inputs
An empty string: s = ""
The loop doesn't run and it returns 0.
k = 0
Every new character makes counts.size 1, which is over 0, so it is removed at once and the window is always empty. It returns 0.
k at least the number of different letters: s = "abcab", k = 5
The rule is never broken, nothing is removed, and it returns the whole length, 5.
Upper and lower case: s = "aA", k = 1
"a" and "A" are different keys, so it returns 1. Lowercase the string first if case shouldn't matter.
Emoji: s = "😀😀", k = 1
s[right] reads UTF-16 code units, and each emoji is two of them, so s.length is 4 and the map sees two different halves. It returns 1 instead of 2. Loop over Array.from(s) to work with whole characters.

Variations and follow-ups

Twists interviewers add

Longest part with no repeats

Shrink while the character just added has a count above 1, instead of while counts.size > k. A plain object or a last-seen index map can make it even shorter: jump left straight past the earlier copy.

Finding rearrangements of a word

Slide a fixed window the length of the word and keep a number matched of letters whose window count equals the word's count. Update matched only for the letter that enters and the letter that leaves, and record a hit when it equals the number of distinct letters in the word.

Shortest window containing every letter of a word

Grow until the window holds every needed letter with enough copies, tracked with a need map and a counter, then shrink from the left while it still does, recording the shortest. This is the "shortest valid window" form of the same pattern.

At most k changes

For the longest part you can make all one letter by changing at most k characters, keep counts and the highest count seen. The window is valid while its size minus that highest count is at most k.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "substring" or "subarray" plus words about contents: "at most k distinct", "no repeating", "contains all characters of", or "anagram of".
  • Say the two jobs of the map out loud: counts tell you whether a character is still inside after one copy leaves, and deleting at zero keeps counts.size equal to the number of distinct values.
  • Test by hand: k = 0, a string with fewer than k distinct letters, and a step where the left edge has to pass several copies of one letter before a key is deleted, like the 4 removals in the trace.
  • Expect the follow-up "what if the input is only lowercase letters?". The answer: use an array of 26 counts and keep your own count of non-zero entries, which avoids hashing and makes space O(1).

Where frontend code uses it

The same idea in real UI code
  • Autocomplete and spell-check features compare letter counts in a moving part of the text to find rearranged words.
  • Analytics code that finds the longest part of a session where a user touched at most two different features counts feature ids in a sliding window.
  • Text editors and linters that flag repeated words or characters within a short stretch of text track recent counts in a window.

Related algorithms