AlgoViz
HomeStrings

Count Number of Substrings

Easy

atMost(k) minus atMost(k-1)

Problem

Count substrings that contain exactly k distinct characters.

In simple words

Substrings with exactly k distinct = (at most k) minus (at most k-1) distinct.

The idea

A sliding window cannot enforce 'exactly k distinct' directly, but it handles 'at most k' easily with a frequency map. Subtracting the at-most-(k-1) count leaves exactly the substrings with k distinct characters.

The trick

  • exactly(k) = atMost(k) - atMost(k-1).
  • In atMost, each right edge adds (right - left + 1) substrings.
  • O(n) per pass.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

2
0

Step 1 of 2. Here's the example — s='aba', k=2 Values: 2.

1/2
Optimal
timeO(n)spaceO(1)
1atMost(k): sliding window counting substrings with <=k distinct2answer = atMost(k) - atMost(k-1)

Input

array
[2]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
s='aba', k=2
Output:
3

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.