Untitled

// Count number of substrings having at least K distinct characters

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

int atleastkDistinctChars(string s , int k){
    
    // using the sliding window and two pointers , hashing
    
    int left = 0;
    int right = 0;
    int count = 0;
    int n = s.size();
    unordered_map<char , int> mp;
    
    while(right < n){
        
        char ch = s[right];
        mp[ch]++;
        
        // if mp.size() is less than k I dont need to count this as a substring
        
        // if mp.size() >= k than , we stand a chance to count the no of substring
        
        while(mp.size() >= k){
            
            count += (n - right);
            char character = s[left];
            mp[character]--;
            
            if(mp[character] == 0){
                mp.erase(character);
            }
            
            left++;
        }
        
        right++;
    }
    
    return count;
    
}

int main(){
    
    string S = "abcca";
    int K = 3;
    cout << atleastkDistinctChars(S, K) << endl;
    return 0;
}