Count Substrings with At Most K Unique Characters

The problem. Given a string s and a number k, count the substrings that contain at most k distinct characters. Two follow-ups are asked just as often, and the same tool solves them: exactly k distinct characters, and at least k. All three are in this lesson.

Example

s = "aabcb",  k = 2  ->  11
s = "aabcd",  k = 2  ->  10
s = "abc",    k = 1  ->  3     ("a", "b", "c")

A string of length n has n(n + 1) / 2 substrings — n that start at index 0, n − 1 at index 1, and so on down to 1. For "aabcb" that's 5 + 4 + 3 + 2 + 1 = 15.