Count of substrings of length K with exactly K distinct characters | Function to return the required count of substrings ; Store the count ; Store the count of distinct characters in every window ; Store the frequency of the first K length substring ; Increase frequency of i - th character ; If K distinct characters exist ; Traverse the rest of the substring ; Increase the frequency of the last character of the current substring ; Decrease the frequency of the first character of the previous substring ; If the character is not present in the current substring ; If the count of distinct characters is 0 ; Return the count ; Driver code ; string str ; Integer K ; Print the count of K length substrings with k distinct characters
def countSubstrings ( str , K ) : NEW_LINE INDENT N = len ( str ) NEW_LINE answer = 0 NEW_LINE map = { } NEW_LINE for i in range ( K ) : NEW_LINE INDENT map [ str [ i ] ] = map . get ( str [ i ] , 0 ) + 1 NEW_LINE DEDENT if ( len ( map ) == K ) : NEW_LINE INDENT answer += 1 NEW_LINE DEDENT for i in range ( K , N ) : NEW_LINE INDENT map [ str [ i ] ] = map . get ( str [ i ] , 0 ) + 1 NEW_LINE map [ str [ i - K ] ] -= 1 NEW_LINE if ( map [ str [ i - K ] ] == 0 ) : NEW_LINE INDENT del map [ str [ i - K ] ] NEW_LINE DEDENT if ( len ( map ) == K ) : NEW_LINE INDENT answer += 1 NEW_LINE DEDENT DEDENT return answer NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT str = " aabcdabbcdc " NEW_LINE K = 3 NEW_LINE print ( countSubstrings ( str , K ) ) NEW_LINE DEDENT