Number of substrings with count of each character as k |
from collections import defaultdict NEW_LINE def have_same_frequency ( freq : defaultdict , k : int ) : NEW_LINE INDENT return all ( [ freq [ i ] == k or freq [ i ] == 0 for i in freq ] ) NEW_LINE DEDENT def count_substrings ( s : str , k : int ) -> int : NEW_LINE INDENT count = 0 NEW_LINE distinct = len ( set ( [ i for i in s ] ) ) NEW_LINE for length in range ( 1 , distinct + 1 ) : NEW_LINE INDENT window_length = length * k NEW_LINE freq = defaultdict ( int ) NEW_LINE window_start = 0 NEW_LINE window_end = window_start + window_length - 1 NEW_LINE for i in range ( window_start , min ( window_end + 1 , len ( s ) ) ) : NEW_LINE INDENT freq [ s [ i ] ] += 1 NEW_LINE DEDENT while window_end < len ( s ) : NEW_LINE INDENT if have_same_frequency ( freq , k ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT freq [ s [ window_start ] ] -= 1 NEW_LINE window_start += 1 NEW_LINE window_end += 1 NEW_LINE if window_end < len ( s ) : NEW_LINE INDENT freq [ s [ window_end ] ] += 1 NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = " aabbcc " NEW_LINE k = 2 NEW_LINE print ( count_substrings ( s , k ) ) NEW_LINE s = " aabbc " NEW_LINE k = 2 NEW_LINE print ( count_substrings ( s , k ) ) NEW_LINE DEDENT