Count number of substrings having at least K distinct characters | Java 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
import java . util . * ; class GFG { static void atleastkDistinctChars ( String s , int k ) { int n = s . length ( ) ; Map < Character , Integer > mp = new HashMap < > ( ) ; int begin = 0 , end = 0 ; int ans = 0 ; while ( end < n ) { char c = s . charAt ( end ) ; mp . put ( c , mp . getOrDefault ( c , 0 ) + 1 ) ; end ++ ; while ( mp . size ( ) >= k ) { char pre = s . charAt ( begin ) ; mp . put ( pre , mp . getOrDefault ( pre , 0 ) - 1 ) ; if ( mp . get ( pre ) == 0 ) { mp . remove ( pre ) ; } ans += s . length ( ) - end + 1 ; begin ++ ; } } System . out . println ( ans ) ; } public static void main ( String [ ] args ) { String S = " abcca " ; int K = 3 ; atleastkDistinctChars ( S , K ) ; } }