Sliding window with a frequency map

Why this matters

Many questions ask for the longest part of a text, or of a list, that meets a rule. Examples are the longest run of letters that uses at most two kinds of letter, or the longest stretch of a shop's sales that comes from at most three product types. A first attempt is often to try every start and every end, then check each part. For a text of 10,000 letters that means about 50 million parts, and each check reads the letters again. The sliding window technique finds the same answer while reading each letter only a small number of times.

This lesson covers one version of the problem. A window may hold at most k different letters, where k is a number you choose. To count the letters in the window, you keep a map from each letter to how many times it appears. The lesson on hash containers covers how unordered_map stores keys. Here you only need two facts. counts[key] gives the count for that key, and a key that was never used starts at 0.

The next lesson, on isomorphic strings, uses two maps to check a rule in both directions. This lesson uses one map and one number that tracks how many keys are non-zero.

The idea: a window with two ends

A window is a stretch of a text with no gaps. Its two ends are called left and right. Both ends start at the first letter. The window holds every letter from left up to and including right.

The rule for this lesson is that the window may hold at most k distinct letters. A letter counts once, however many times it appears. The text aab has two distinct letters, a and b.

Three pieces of state keep the window up to date:

• count: a map from each letter to how many times it appears in the window.
• distinct: a number that holds how many letters have a count above zero.
• left and right: the two ends of the window.

The procedure repeats three steps for each new value of right, from the first letter to the last.

1. Add the letter at right to the window. If its count was 0 before, distinct goes up by one.
2. While distinct is more than k, remove the letter at left from the window. If its count becomes 0, distinct goes down by one. Then move left forward by one.
3. The window now holds at most k distinct letters. Its length is right - left + 1. Keep the largest length seen so far.

Both ends only move forward. right moves forward one step for each letter in the text. left also moves forward and never goes back. Each letter enters the window once and leaves at most once, so the total number of steps is about twice the length of the text. Each map lookup takes about the same time on average, however big the map is, so the whole run takes O(n) time, where n is the number of letters. O(n) means that doubling the text roughly doubles the work.

Worked example by hand

Take the text aabacbebebe and set k to 2. Start with an empty window, with left at 0 and right at 0.

• right is 0 and the letter is a. Its count goes from 0 to 1, so distinct becomes 1. The window is a, with length 1.
• right is 1 and the letter is a. Its count goes to 2. distinct stays 1. The window is aa, with length 2.
• right is 2 and the letter is b. Its count goes to 1, so distinct becomes 2. The window is aab, with length 3. Two distinct letters is still allowed.
• right is 3 and the letter is a. Its count goes to 3. distinct stays 2. The window is aaba, with length 4.
• right is 4 and the letter is c. Its count goes to 1, so distinct becomes 3. That is too many, so shrink from the left.
  • Remove the a at position 0. Its count goes from 3 to 2, and distinct stays 3. Move left to 1.
  • Remove the a at position 1. Its count goes from 2 to 1, and distinct stays 3. Move left to 2.
  • Remove the b at position 2. Its count goes from 1 to 0, so distinct drops to 2. Move left to 3.
• The window is now ac, at positions 3 and 4, with length 2.

Continue the same way and the longest valid window for this text is bebebe, with length 6. The program in the first example prints each of these windows, so you can check the walkthrough against it.

Example one: the longest window with at most k distinct letters

The program below follows the three steps. It also prints the window after each step, so you can match it with the walkthrough. A real solution would not print these lines.

The output is:

right=0 char=a window="a" distinct=1
right=1 char=a window="aa" distinct=1
right=2 char=b window="aab" distinct=2
right=3 char=a window="aaba" distinct=2
right=4 char=c window="ac" distinct=2
right=5 char=b window="cb" distinct=2
right=6 char=e window="be" distinct=2
right=7 char=b window="beb" distinct=2
right=8 char=e window="bebe" distinct=2
right=9 char=b window="bebeb" distinct=2
right=10 char=e window="bebebe" distinct=2
6
right=0 char=e window="e" distinct=1
right=1 char=c window="ec" distinct=2
right=2 char=e window="ece" distinct=2
right=3 char=b window="eb" distinct=2
right=4 char=a window="ba" distinct=2
3
0
right=0 char=a window="" distinct=0
right=1 char=b window="" distinct=0
right=2 char=c window="" distinct=0
0

The first answer is 6, from the window bebebe. The second answer is 3, from ece. The empty text gives 0. With k set to 0, no letter is allowed, so every window is empty and the answer is 0. The trace shows the empty windows for that last call.

Some lines in the code need a closer look.

unordered_map<char, size_t> count; makes a hash map. Each key is a character and each value is a count. The type size_t is an unsigned whole number that the standard library uses for sizes and positions. Using it everywhere avoids the sign warnings shown in the mistakes section.

if (count[c] == 0) ++distinct; runs before the count goes up. It reads 0 for a letter that has not been seen in the window, so the distinct counter goes up only when a new letter arrives.

--count[out]; followed by if (count[out] == 0) --distinct; is the reverse. The distinct counter goes down only when the last copy of a letter leaves the window.

s.substr(left, right - left + 1) returns the window as a new string. It is used here only for the printed trace.

Example two: return where the window is

The answer is often more useful as a position than as a number. A caller may want the substring itself. The next program returns a small struct, which is a plain group of named fields. It holds the start position and the length of the best window. Only the best window is kept, so the program does not build a new string for each step.

The output is:

start=5 length=6
substring=bebebe
start=0 length=1
substring=a

The first window starts at position 5 and has length 6, so the substring is bebebe. For abcd with k set to 1, every window of length 2 or more has two letters, so the first single letter wins. The > in the check keeps the first window of the longest length, so ties go to the earlier window.

The line Window best{0, 0}; uses brace syntax to set both fields at once. The line best = {left, right - left + 1}; builds a new Window from the two values and copies it in.

Example three: counting every valid window

Sometimes the question is how many windows are valid, not which one is longest. For example, how many substrings of abcabc have at most two distinct letters?

Here is a useful idea. For each right, the windows that end at right and have at most k distinct letters start somewhere between left and right. There are right - left + 1 such starts, and each one gives one valid window. So the program adds right - left + 1 to a running total at each step. The left value is the earliest valid start, so no valid start is missed. The static_cast<long long> turns the window length from size_t into long long, the type of total.

Counting exactly k distinct letters is harder to do in one pass. The trick is to subtract two counts. The number of windows with exactly k distinct letters equals the number with at most k, minus the number with at most k - 1.

The output is:

atMost(2) for abcabc: 11
atMost(1) for abcabc: 6
exactly 2 for abcabc: 5
exactly 1 for abcabc: 6
exactly 3 for abcabc: 10

You can check the exact count by hand. The substrings of abcabc with exactly two distinct letters are the five substrings of length 2: ab, bc, ca, ab and bc. No substring of length 3 or more has exactly two distinct letters, because each run of three letters in this text has three different letters. The answer 5 matches.

The answer for exactly 1 is 6, one for each single letter. The answer for exactly 3 is 10. It equals the number of substrings of length 3 or more, since every such substring of abcabc has all three letters.

Note that countExactlyK calls k - 1. When k is 0, that value would wrap around to a very large number, so this function should only be called with k of 1 or more.

Common mistakes

Mistake one: shrinking with if instead of while

The shrink step must keep going until the window is valid again. Removing one letter is not always enough. Take the window aabac from the walkthrough, which holds three letters. Removing one a leaves abac, which still holds three letters. Removing the second a leaves bac, which still holds three. Only after removing the b does the window become valid.

Using if removes at most one letter per step. With bba and k set to 1, the window reaches ba at the last step. It still holds two letters, but the program keeps it. The program below counts the windows with if and prints the wrong number.

The output is:

5

The correct count is 4. The valid windows of bba with at most one distinct letter are b, b, bb, and a. The program with if counts 5 because it also counts ba. The window ba has two letters, so it is not valid. The fix is to change if to while.

Mistake two: counting the distinct letters with the size of the map

It is tempting to write count.size() in place of the distinct counter. That works only if every key leaves the map when its count reaches 0. A map does not remove a key just because its value is 0. The key stays, so size() never goes down. The loop then keeps moving left past the end of the window, and the program reads outside the text.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
 
size_t buggyLongest(const string& s, size_t k) {
    unordered_map<char, size_t> count;
    size_t best = 0;
    size_t left = 0;
    for (size_t right = 0; right < s.size(); ++right) {
        ++count[s[right]];
        while (count.size() > k) {
            char out = s[left];
            if (--count[out] == 0) {
                // the key stays in the map with value 0
            }
            ++left;
        }
        if (right - left + 1 > best) best = right - left + 1;
    }
    return best;
}
 
int main() {
    cout << buggyLongest("aabacbebebe", 2) << "\n";
}

Compiled with g++ -std=c++20 -Wall, the program runs and stops with this message on the Ubuntu build used for this lesson. The message is cut short here. The middle part repeats the function signature.

/usr/include/c++/15/bits/basic_string.h:1349: ... operator[](size_type) const ...: Assertion '__pos <= size()' failed.

The process ends with exit code 134, which means it was stopped by an abort signal. Other builds may not print the assertion, but the program still reads past the end of the text, which is undefined behaviour. The fix is to keep a separate distinct counter and to change it only when a count moves between 0 and 1. The first example in this lesson does that.

Mistake three: comparing an int with a size

The map's size() returns an unsigned value. If you store the limit in an int, the compiler warns about the comparison. This program is short, but the same thing happens in a longer solution.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
 
int main() {
    string s = "aabacbebebe";
    int k = 2;
    unordered_map<char, size_t> count;
    for (char c : s) ++count[c];
    if (count.size() > k) cout << "too many\n";
    cout << "size " << count.size() << "\n";
}

Compiled with g++ -std=c++20 -Wall, the compiler prints this warning:

signed_size.cpp: In function ‘int main()’:
signed_size.cpp:11:22: warning: comparison of integer expressions of different signedness: ‘std::unordered_map<char, long unsigned int>::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
   11 |     if (count.size() > k) cout << "too many\n";
      |         ~~~~~~~~~~~~~^~~

The comparison works here, but a negative k would be read as a huge unsigned number. Store k as size_t, as the examples in this lesson do, and the warning goes away.

Practice

Exercise 1. Find the length of the longest window in aaabbbaa that holds at most one distinct letter.

Show the answer

The answer is 3. The runs aaa and bbb each have length 3. The final aa has length 2.

Exercise 2. Count the substrings of aabbb that hold exactly one distinct letter.

Show the answer

The answer is 9. The run aa gives 3 substrings: a, a and aa. The run bbb gives 6 substrings: three single b letters, two bb substrings and one bbb. The total is 9.

Exercise 3. For the text aabacbebebe, find the length of the longest window that holds at most three distinct letters.

Show the answer

The answer is 7. The window cbebebe, which starts at position 4, holds the three letters c, b and e. The first example prints a trace for k set to 2. Running the same method with k set to 3 gives 7.

Exercise 4. Count the substrings of abcba that hold exactly two distinct letters.

Show the answer

The answer is 5. The length-2 substrings are ab, bc, cb and ba, which are four. The length-3 substring bcb is the fifth. The substrings abc and cba each have three letters.

Exercise 5. A list of fruit types is written as the characters 1212322. A basket may hold at most two kinds of fruit. Find the length of the longest run of fruit that fits in one basket.

Show the answer

The answer is 4. Two windows reach length 4: 1212 and 2322. No window of length 5 holds at most two kinds of fruit. The first example returns 4 for this text when k is 2.

Summary

• A sliding window keeps two ends that only move forward, so each letter enters and leaves once.
• A map of counts plus a distinct counter tells you how many letters are inside the window.
• Use while when shrinking, since one removal may not restore the rule.
• The count of windows with exactly k distinct letters equals the count with at most k, minus the count with at most k - 1.
• Keep the distinct counter separate from the map size, because a key with count 0 stays in the map.