Sliding Window Character Frequency and Satisfaction Tracking

Recommended resources

The freely available resources this lesson will direct you to.

Hello! In our last lesson, we mastered the variable-size sliding window, where the window expanded and shrank based on a simple, monotonic property like a running sum. This was a powerful step up from fixed-size windows.

Today, we'll build on that foundation to handle more complex criteria within the window. We're moving beyond simple sums to track the counts of multiple different characters. The goal for this lesson is to learn how to maintain character frequencies and a satisfaction count inside a sliding window. This "satisfaction count" is a crucial optimization that allows us to check if our window meets complex requirements in constant time, keeping our overall solution efficient and linear.

We'll center our discussion around a classic problem: finding if a permutation of one string exists as a substring within another.

The Problem: Permutation in a String

Let's consider the problem:

Given two strings, s1 and s2, return true if s2 contains a permutation of s1, and false otherwise.

For example, if s1 = "ab" and s2 = "eidbaooo", the answer is true because s2 contains "ba", which is a permutation of s1.

The key insight is that two strings are permutations of each other if and only if they have the same character counts. So, the problem becomes: find a substring in s2 that has the same length and character frequencies as s1.

This is a perfect fit for a sliding window. We can slide a window of size len(s1) across s2. But how do we efficiently check if the characters in the window match the frequencies of s1 at every step? Comparing two full frequency maps (e.g., hash maps) at each of the N steps would be too slow, resulting in an O(N * |Σ|) complexity, where |Σ| is the size of the character set (e.g., 26 for lowercase English letters). We need a faster way to check for a match.

The O(N) Solution: Satisfaction Count

The efficient solution is to maintain a "satisfaction count"—a single variable that tells us if the window's character counts match the target's counts. Instead of re-comparing the entire maps, we just check this one variable.

The following video by NeetCode provides an excellent explanation. It starts by discussing the less optimal approach of comparing hashmaps and then introduces the matches variable (our satisfaction count) to achieve a true O(N) solution.

Permutation in String - Leetcode 567 - Python

Watch this video to understand the core logic. The presenter will walk you through the "Permutation in String" problem (LeetCode 567). Pay close attention to these parts: Problem setup and why it's an "anagram" problem: the explanation. The initial idea of using two hashmaps and comparing them, which is slightly suboptimal: the first approach. The key optimization using a matches variable to avoid full comparisons. This is the main takeaway: the 'matches' variable.

The presenter uses Python, but the logic is universal. Focus on how the matches count is incremented and decremented as characters enter and leave the window. This is the essence of maintaining a satisfaction count.

Did you see how the matches variable acts as a shortcut? We only need to check if matches === 26. This O(1) check is what makes the whole algorithm run in linear time.

A General Framework: `need` and `valid`

The matches variable in the NeetCode video is one way to implement a satisfaction count. A slightly more general and extremely powerful way to think about this is using two data structures:

A need map, storing the frequency of characters required by the target string (s1).
A window map, storing the frequency of characters inside our current sliding window.

And to tie them together, we use a valid count. This variable tracks how many character types in our window have met the need requirement.

Labuladong's famous sliding window template is built on this exact need/valid pattern. It's a versatile framework that can solve many problems, including both fixed-size window problems like "Permutation in String" and variable-size window problems.

Let's study this framework. We'll use the "Minimum Window Substring" problem as an example because it showcases the full power of this pattern with a variable-size window.

Sliding Window Algorithm Code Template - Labuladong Algo Notes

This article section explains the need and valid pattern in detail. It's one of the most effective mental models for solving sliding window problems.

Start reading from the section "1. Minimum Window Substring". Read through the explanation of the logic: how the window expands, how the need and window maps are used, and crucially, how the valid count is updated. Follow the logic down to the complete code block. Pay attention to the symmetry: how adding a character is the inverse of removing one. The valid count is incremented when a character's count in the window exactly matches its needed count. It's decremented when a character that was previously satisfied is removed, making its count no longer sufficient.

For a JavaScript-specific walkthrough of this same "Minimum Window Substring" problem, the following video is a great resource. It implements the same logic with a Map and a count variable (equivalent to our valid count).

Minimum Window Substring - LeetCode 76 - JavaScript

This video by AlgoJS will show you a clean JavaScript implementation of the need/valid pattern for a variable-size window. Focus on these segments: The Core Idea: The introduction of the frequency map and the two-pointer approach to achieve O(m+n) complexity. Watch this part. The Walkthrough: A step-by-step trace of how the window expands and contracts, and how the count variable is updated when requirements are met or unmet. Follow the example.

Notice how he handles updating the count only when a character's frequency in the map crosses the zero threshold. This is the heart of the satisfaction count mechanism.

Applying the Framework to "Permutation in String"

Now, let's bring it all together and apply this robust need/valid pattern to our original "Permutation in String" problem. This problem uses a fixed-size window, which slightly simplifies the template's logic.

The following resource provides a fantastic explanation, a TypeScript implementation, and a discussion of common pitfalls.

567. Permutation in String - In-Depth Explanation

This article from Algo.monster will provide us with a solid implementation and highlight critical details to avoid bugs.

First, read the Intuition section to connect the problem to character frequencies and sliding windows. Next, examine the Solution Approach and Algorithm Steps. This article uses cnt (our need map) and need (our valid or satisfaction count). It's the same pattern, just with slightly different variable names. Study how need is decremented when a character's count hits zero and incremented when it becomes non-zero after a character leaves the window. Find the algorithm steps. Then, review the TypeScript implementation. Notice it uses an array charFrequency instead of a Map, a common optimization when the character set is a known, small range like 'a'-'z'. Here, uniqueCharsNeeded is the satisfaction count. Finally, and this is very important, read the Common Pitfalls section. Pay special attention to Pitfall 1 and Pitfall 2. Understanding these will help you avoid off-by-one errors and logical bugs in your own implementations.

Conclusion

In this lesson, we've added a critical tool to our sliding window toolkit. By tracking character frequencies and using a satisfaction count, we can now solve a whole new class of problems that involve matching complex criteria within a window.

Key Takeaways:

Frequency Map: For problems involving character counts or anagrams, a hash map (or an array for a fixed charset) is the go-to data structure to maintain inside the window.
Satisfaction Count: Instead of comparing entire frequency maps at each step, we maintain a single counter (matches, valid, uniqueCharsNeeded, etc.). This counter tracks how many requirements are currently met by the window.
O(1) Updates: The satisfaction count is updated only when a character's frequency in the window crosses a critical threshold (e.g., its count becomes equal to what's needed, or becomes non-zero after a character is removed). This makes the validity check an O(1) operation.
O(N) Complexity: Combining the sliding window motion (where each element is touched at most twice) with O(1) updates gives us an overall linear time complexity, O(N).

The pattern we analyzed in "Minimum Window Substring" is a very common and important one. In our next lesson, we will focus explicitly on this pattern: finding a minimum valid substring by tracking fulfilled requirements. You've already seen the core mechanics today, and next time we will formalize it as a distinct pattern.