Count number of substrings with exactly k distinct characters | C ++ program to count number of substrings with exactly k distinct characters in a given string ; Function to count number of substrings with exactly k unique characters ; Initialize result ; To store count of characters from ' a ' to ' z ' ; Consider all substrings beginning with str [ i ] ; Initializing array with 0 ; Consider all substrings between str [ i . . j ] ; If this is a new character for this substring , increment dist_count . ; Increment count of current character ; If distinct character count becomes k , then increment result . ; Driver Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countkDist ( string str , int k ) { int n = str . length ( ) ; int res = 0 ; int cnt [ 26 ] ; for ( int i = 0 ; i < n ; i ++ ) { int dist_count = 0 ; memset ( cnt , 0 , sizeof ( cnt ) ) ; for ( int j = i ; j < n ; j ++ ) { if ( cnt [ str [ j ] - ' a ' ] == 0 ) dist_count ++ ; cnt [ str [ j ] - ' a ' ] ++ ; if ( dist_count == k ) res ++ ; if ( dist_count > k ) break ; } } return res ; } int main ( ) { string str = " abcbaa " ; int k = 3 ; cout << " Total ▁ substrings ▁ with ▁ exactly ▁ " << k << " ▁ distinct ▁ characters ▁ : " << countkDist ( str , k ) << endl ; return 0 ; }