Number of Substrings in String of 0s and 1s that have K 1s

In this article, we have explored algorithm to find the Number of Substrings in a String of 0's and 1's that have 'K' number of 1's.

Table of contents:

Problem StatementBrute Force approachEfficient approach

Pre-requisite:

Prefix Sum ArrayProblem Statement

Input :
i) A String of 0's and 1's
ii) A integer 'K'

Output : Number of substrings that have 'K' number of 1's

Example 1:

Input : "101010",K=2Output : 6 Substrings are "101" [0,2],"1010" [0,3],"0101" [1,4],"01010" [1,5],"101" [2,4] a...