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 count 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
< ? php function countkDist ( $ str , $ k ) { $ res = 0 ; $ n = strlen ( $ str ) ; $ cnt = array ( ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ dist_count = 0 ; $ cnt = array_fill ( 0 , 0 , true ) ; for ( $ j = $ i ; $ j < $ n ; $ j ++ ) { if ( $ cnt [ ord ( $ str [ $ j ] ) - ord ( ' a ' ) ] == 0 ) $ dist_count ++ ; $ cnt [ ord ( $ str [ $ j ] ) - ord ( ' a ' ) ] ++ ; if ( $ dist_count == $ k ) $ res ++ ; } } return $ res ; } { $ ch = " abcbaa " ; $ k = 3 ; echo ( " Total ▁ substrings ▁ with ▁ exactly ▁ " . $ k . " ▁ distinct ▁ characters ▁ : ▁ " . countkDist ( $ ch , $ k ) ) ; }