Count of substrings of a binary string containing K ones | Java program to find count of substring containing exactly 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 to test above methods
import java . io . * ; public class GFG { static int countOfSubstringWithKOnes ( String s , int K ) { int N = s . length ( ) ; int res = 0 ; int countOfOne = 0 ; int [ ] freq = new int [ N + 1 ] ; freq [ 0 ] = 1 ; for ( int i = 0 ; i < N ; i ++ ) { countOfOne += ( s . charAt ( i ) - '0' ) ; if ( countOfOne >= K ) { res += freq [ countOfOne - K ] ; } freq [ countOfOne ] ++ ; } return res ; } static public void main ( String [ ] args ) { String s = "10010" ; int K = 1 ; System . out . println ( countOfSubstringWithKOnes ( s , K ) ) ; } }