Count of substrings of a binary string containing K ones | method returns total number of substring having K ones ; initialize index having zero sum as 1 ; loop over binary characters of string ; update countOfOne variable with value of ith character ; if value reaches more than K , then update result ; add frequency of indices , having sum ( current sum - K ) , to the result ; update frequency of one 's count ; Driver code
def countOfSubstringWithKOnes ( s , K ) : NEW_LINE INDENT N = len ( s ) NEW_LINE res = 0 NEW_LINE countOfOne = 0 NEW_LINE freq = [ 0 for i in range ( N + 1 ) ] NEW_LINE freq [ 0 ] = 1 NEW_LINE for i in range ( 0 , N , 1 ) : NEW_LINE INDENT countOfOne += ord ( s [ i ] ) - ord ( '0' ) NEW_LINE if ( countOfOne >= K ) : NEW_LINE INDENT res += freq [ countOfOne - K ] NEW_LINE DEDENT freq [ countOfOne ] += 1 NEW_LINE DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = "10010" NEW_LINE K = 1 NEW_LINE print ( countOfSubstringWithKOnes ( s , K ) ) NEW_LINE DEDENT