Count number of substrings having at least K distinct characters | Python 3 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
from collections import defaultdict NEW_LINE def atleastkDistinctChars ( s , k ) : NEW_LINE INDENT n = len ( s ) NEW_LINE mp = defaultdict ( int ) NEW_LINE begin = 0 NEW_LINE end = 0 NEW_LINE ans = 0 NEW_LINE while ( end < n ) : NEW_LINE INDENT c = s [ end ] NEW_LINE mp += 1 NEW_LINE end += 1 NEW_LINE while ( len ( mp ) >= k ) : NEW_LINE INDENT pre = s [ begin ] NEW_LINE mp [ pre ] -= 1 NEW_LINE if ( mp [ pre ] == 0 ) : NEW_LINE INDENT del mp [ pre ] NEW_LINE DEDENT ans += len ( s ) - end + 1 NEW_LINE begin += 1 NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = " abcca " NEW_LINE K = 3 NEW_LINE atleastkDistinctChars ( S , K ) NEW_LINE DEDENT