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
< ? php function countOfSubstringWithKOnes ( $ s , $ K ) { $ N = strlen ( $ s ) ; $ res = 0 ; $ countOfOne = 0 ; $ freq = array ( ) ; for ( $ i = 0 ; $ i <= $ N ; $ i ++ ) $ freq [ $ i ] = 0 ; $ freq [ 0 ] = 1 ; for ( $ i = 0 ; $ i < $ N ; $ i ++ ) { $ countOfOne += ( $ s [ $ i ] - '0' ) ; if ( $ countOfOne >= $ K ) { $ res = $ res + $ freq [ $ countOfOne - $ K ] ; } $ freq [ $ countOfOne ] ++ ; } return $ res ; } $ s = "10010" ; $ K = 1 ; echo countOfSubstringWithKOnes ( $ s , $ K ) , " " ; ? >