Count substrings with each character occurring at most k times | Python 3 program to count number of substrings in which each character has count less than or equal to k . ; variable to store count of substrings . ; array to store count of each character . ; increment character count ; check only the count of current character because only the count of this character is changed . The ending point is incremented to current position only if all other characters have count at most k and hence their count is not checked . If count is less than k , then increase ans by 1. ; if count is less than k , then break as subsequent substrings for this starting point will also have count greater than k and hence are reduntant to check . ; return the final count of substrings . ; Driver code
def findSubstrings ( s , k ) : NEW_LINE INDENT ans = 0 NEW_LINE n = len ( s ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT cnt = [ 0 ] * 26 NEW_LINE for j in range ( i , n ) : NEW_LINE INDENT cnt [ ord ( s [ j ] ) - ord ( ' a ' ) ] += 1 NEW_LINE if ( cnt [ ord ( s [ j ] ) - ord ( ' a ' ) ] <= k ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = " aaabb " NEW_LINE k = 2 NEW_LINE print ( findSubstrings ( S , k ) ) NEW_LINE DEDENT