Count number of substrings having at least K distinct characters | C ++ program for the above approach ; Function to count number of substrings having atleast k distinct characters ; Stores the size of the string ; Initialize a HashMap ; Stores the start and end indices of sliding window ; Stores the required result ; Iterate while the end pointer is less than n ; Include the character at the end of the window ; Increment end pointer by 1 ; Iterate until count of distinct characters becomes less than K ; Remove the character from the beginning of window ; If its frequency is 0 , remove it from the map ; Update the answer ; Print the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void atleastkDistinctChars ( string s , int k ) { int n = s . size ( ) ; unordered_map < char , int > mp ; int begin = 0 , end = 0 ; int ans = 0 ; while ( end < n ) { char c = s [ end ] ; mp ++ ; end ++ ; while ( mp . size ( ) >= k ) { char pre = s [ begin ] ; mp [ pre ] -- ; if ( mp [ pre ] == 0 ) { mp . erase ( pre ) ; } ans += s . length ( ) - end + 1 ; begin ++ ; } } cout << ans ; } int main ( ) { string S = " abcca " ; int K = 3 ; atleastkDistinctChars ( S , K ) ; return 0 ; }