Count Substrings with At Most K Zeros and K Ones

Problem Statement

Count Substrings with At Most K Zeros and K Ones Problem Description You are given a string str of length n and an integer k . Your task is to count and print the number of substrings of str which contain at most k 0s and at most k 1s. Note: if k = 0 then print 0. Input Format: The input consists of three lines: The first line contains an integer, i.e. n . The second line contains the string str . The third line contains the integer k . The input will be read from the STDIN by the candidate. Output Format: Print the number of substrings of str which contain at most k 0s and at most k 1s. The output will be matched to the candidate's output printed on the STDOUT. Examples Example 1: Input: 4 0111 2 Output: 8 Explanation: Substrings which contain at most k 0s and at most k 1s are {0, 01, 011, 1, 11, 111, 1}. Thus, output is 8. Sample Input: Input: 8 01110000 1 Sample Output: Output: 10 Constraints 1 ≤ n ≤ 10 5 0 ≤ k ≤ 10 5