Count number of substrings with exactly k distinct characters | 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 Code
def countkDist ( str1 , k ) : NEW_LINE INDENT n = len ( str1 ) NEW_LINE res = 0 NEW_LINE cnt = [ 0 ] * 27 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT dist_count = 0 NEW_LINE cnt = [ 0 ] * 27 NEW_LINE for j in range ( i , n ) : NEW_LINE INDENT if ( cnt [ ord ( str1 [ j ] ) - 97 ] == 0 ) : NEW_LINE INDENT dist_count += 1 NEW_LINE DEDENT cnt [ ord ( str1 [ j ] ) - 97 ] += 1 NEW_LINE if ( dist_count == k ) : NEW_LINE INDENT res += 1 NEW_LINE DEDENT if ( dist_count > k ) : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT DEDENT return res NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT str1 = " abcbaa " NEW_LINE k = 3 NEW_LINE print ( " Total ▁ substrings ▁ with ▁ exactly " , k , " distinct ▁ characters ▁ : ▁ " , end = " " ) NEW_LINE print ( countkDist ( str1 , k ) ) NEW_LINE DEDENT