Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 28

Sliding Window: Substrings with At Most K Distinct Characters

Recommended resources

Hello! In our last session, we mastered the expand-and-contract rhythm of the sliding window to solve the "Minimum Window Substring" problem. This involved finding a single, optimal substring that satisfied a complex condition.

Today, we'll continue our exploration of the sliding window pattern but shift our focus from optimization to counting. Our goal is to count the number of substrings with at most K distinct characters. This problem introduces a new way of using the window's size to count valid substrings efficiently. Mastering this technique is crucial, as it serves as a powerful building block for solving a related and very common interview problem: counting substrings with exactly K distinct characters.

1. Understanding the Problem

Let's first clearly define the task. We are given a string s and a positive integer k. We need to find the total number of substrings of s that contain k or fewer unique characters.

For example, if s = "pqpqs" and k = 2, the substrings with at most 2 distinct characters are:

  • Substrings with 1 distinct character: "p", "q", "p", "q", "s", "qq"
  • Substrings with 2 distinct characters: "pq", "pqp", "pqpq", "qp", "qpq", "pqs", "qs"

Manually listing and counting them is tedious and error-prone. We need a systematic approach.

Count Number of Substrings - Tutorial

The "takeuforward" tutorial, part of the TUF DSA sheet, presents this problem. Note that its main goal is to count substrings with exactly k distinct characters, but it does so by first solving our target problem: counting substrings with at most k distinct characters.

Read the Problem Statement and Examples to solidify your understanding. The examples focus on "exactly k", but keep in mind we'll first solve for "at most k".

2. The Brute-Force Approach

As is our custom, let's begin with the brute-force solution to establish a baseline. The most direct method is to generate every possible substring, check if it satisfies the condition, and increment a counter if it does.

The algorithm is as follows:

  1. Use a nested loop to generate all substrings. The outer loop (i) determines the starting index, and the inner loop (j) determines the ending index.
  2. For each substring s[i...j], count its number of distinct characters. An easy way to do this is to add all its characters to a HashSet and then get the set's size.
  3. If the number of distinct characters is less than or equal to k, increment our total count.

This approach is correct but inefficient. With two nested loops to generate substrings and an inner operation that also depends on the substring length, the time complexity is high.

Count substrings with k distinct characters - GeeksforGeeks

This GeeksforGeeks article provides a clear implementation of the brute-force strategy. The article solves for "exactly k", but the logic is nearly identical for "at most k".

In the section [Naive Approach], read the description of the method. Then, review the provided Java code. Notice how it uses nested loops and a boolean array (acting as a frequency map) to count distinct characters. To adapt this for our problem, you would simply change the condition if (distinctCnt == k) to if (distinctCnt <= k).

The time complexity of this approach is O(N^2), as the inner loop re-evaluates characters for overlapping substrings. This is what we need to optimize.

3. The Optimal Sliding Window Solution

The key weakness of the brute-force method is redundant work. A sliding window avoids this by maintaining a single, dynamic window and using its properties to count substrings efficiently.

The standard "expand-and-contract" logic we used for "Minimum Window Substring" is tricky to adapt for counting because a valid window might contain smaller substrings that are also valid, and we need to count all of them. This is where today's new pattern comes in.

The Counting Insight

Let's say we have a window from index left to right, s[left...right], which is valid (i.e., has at most k distinct characters). If we just added the character at right, how many new valid substrings have we formed?

The new substrings are s[right], s[right-1...right], s[right-2...right], ..., all the way to s[left...right]. Since the largest window s[left...right] is valid, all of these smaller substrings ending at right must also be valid. The number of such substrings is exactly right - left + 1.

This image demonstrates the counting principle. For an array `[1, 2, 1, 2]` and `k=2`, as the right pointer expands, the count is incremented by the size of the current valid window (`right - left + 1`). For example, when the window is `[1, 2, 1]`, its size is 3, and we add 3 to our total count, accounting for the new substrings `[1]`, `[2, 1]`, and `[1, 2, 1]`.

The Algorithm for "At Most K"

With this counting trick, we can define a clean sliding window algorithm:

  1. Initialize left = 0, count = 0, and a HashMap to store character frequencies.
  2. Iterate with a right pointer from 0 to n-1.
  3. Add the character s.charAt(right) to our window and update its frequency in the map.
  4. Shrink the window: While the number of distinct characters in the map (map.size()) is greater than k, we have an invalid window. To fix it, we must shrink from the left:
    • Get the character s.charAt(left).
    • Decrement its frequency in the map.
    • If its frequency becomes 0, remove it from the map entirely.
    • Increment left.
  5. Count substrings: Once the while loop finishes, the window s[left...right] is guaranteed to be valid. We add its size, right - left + 1, to our total count.
  6. Repeat for all right pointers.

This process ensures that for each position right, we count exactly the number of valid substrings that end at that position. Summing these up gives us the total.

The video below gives an excellent dry run of this entire process, from realizing a simple sliding window fails for "exactly K" to discovering the "at most K" counting method.

L11. Subarray with k different integers | 2 Pointers and Sliding Window Playlist

In this video, Striver tackles the problem of counting subarrays with exactly K distinct integers. To do this, he first develops the robust helper function for at most K, which is our focus.

First, watch this segment to understand why the standard expand/shrink pattern we used before is difficult to apply for an "exactly K" counting problem. This motivates a change in strategy. Next, see the new strategy unfold. Watch from this walkthrough, where he explains and demonstrates the count += (right - left + 1) logic for solving the "at most K" problem. This is the core of today's lesson. Pay close attention to how the count is updated at each step of the right pointer. Finally, you can review the pseudo-code for the atMost(K) helper function.

4. From "At Most K" to "Exactly K"

Now for the elegant trick. We've built a function that can count substrings with at most K distinct characters. How can we use this to solve the common interview variant: counting substrings with exactly K distinct characters?

The insight lies in a simple principle of inclusion-exclusion:

count(exactly K) = count(at most K) - count(at most K-1)

If you take all substrings with K or fewer unique characters and subtract all substrings with K-1 or fewer unique characters, you are left with only those that have exactly K unique characters.

This transforms the problem from a difficult direct implementation into two straightforward calls to the helper function we just designed.

Count Number of Substrings - Tutorial

The takeuforward tutorial formalizes this entire process in clean Java code.

First, read the Approach section, which concisely states the atMost(K) - atMost(K-1) strategy. Next, carefully study the Java implementation of the atMostKDistinct helper function. This is the direct translation of the algorithm we just discussed. Then, see how it's used in the main function countSubstrings. Finally, review the complexity analysis. Since each pointer traverses the string once, the time complexity is O(N). Because we call the function twice, it's technically O(2N), which simplifies to O(N). The space complexity is O(K) for the HashMap.

This pattern of converting an "exactly K" problem into two "at most K" problems is a fundamental technique in sliding window and prefix sum problems, and recognizing it can save you a lot of time in an interview.

Conclusion

In this lesson, we expanded our sliding window toolkit by learning a new pattern focused on counting. We distinguished this from the optimization-focused patterns we've seen before.

Key Takeaways:

  • Counting vs. Optimizing: Sliding window problems can involve finding an optimal window (e.g., longest, shortest) or counting all valid windows.
  • The "At Most K" Counting Pattern: For a valid window s[left...right], the number of valid substrings ending at right is right - left + 1. By adding this to a running total at each step of the right pointer, we can count all valid substrings in linear time.
  • Problem Transformation: A difficult problem like "count substrings with exactly K distinct characters" can often be solved by transforming it into count(at most K) - count(at most K-1). This is a powerful problem-solving insight.
  • Implementation: A HashMap is the ideal data structure to track character frequencies and the count of distinct elements (map.size()) within the window.

Our next lesson will venture into a different area of string algorithms: efficient pattern searching. We will explore sophisticated algorithms like KMP or the Z-algorithm, which are designed to find occurrences of a smaller pattern string within a larger text in linear time, a classic problem in computer science.