Algorithm

Define a helper function atMostKDistinct(s, k):

Use a sliding window with two pointers (left and right) and a frequency map.
Expand the window by moving the right pointer and count characters.
If the count of distinct characters exceeds k, shrink the window by moving the left pointer.
For each valid window, add (right - left + 1) to the result.

To find substrings with exactly k distinct characters, calculate:

atMostKDistinct(s, k) - atMostKDistinct(s, k-1)

Code

#include <bits/stdc++.h>
using namespace std;

// Function to count substrings with at most k distinct characters
int atMostKDistinct(string s, int k) {
    // Left pointer and result
    int left = 0, res = 0;
    // Frequency map
    unordered_map<char, int> freq;

    // Iterate throu