Count of substrings of length K with exactly K distinct characters | C ++ program to find the count of k length substrings with k distinct characters using sliding window ; Function to return the required count of substrings ; Store the count ; Store the count of distinct characters in every window ; Store the frequency of the first K length substring ; Increase frequency of i - th character ; If K distinct characters exist ; Traverse the rest of the substring ; Increase the frequency of the last character of the current substring ; Decrease the frequency of the first character of the previous substring ; If the character is not present in the current substring ; If the count of distinct characters is 0 ; Return the count ; Driver code ; string str ; integer K ; Print the count of K length substrings with k distinct characters
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countSubstrings ( string str , int K ) { int N = str . size ( ) ; int answer = 0 ; unordered_map < char , int > map ; for ( int i = 0 ; i < K ; i ++ ) { map [ str [ i ] ] ++ ; } if ( map . size ( ) == K ) answer ++ ; for ( int i = K ; i < N ; i ++ ) { map [ str [ i ] ] ++ ; map [ str [ i - K ] ] -- ; if ( map [ str [ i - K ] ] == 0 ) { map . erase ( str [ i - K ] ) ; } if ( map . size ( ) == K ) { answer ++ ; } } return answer ; } int main ( ) { string str = " aabcdabbcdc " ; int K = 3 ; cout << countSubstrings ( str , K ) << endl ; return 0 ; }