742. Another String Problem
0
Medium
A binary string consists only of the characters "0" and "1".
A substring v is a part of string w if it has a non-zero length and can be found starting from any position in string w. For example, the string "010" has six substrings: "0", "1", "0", "01", "10", "010". Two substrings are considered different if their positions of occurrence are different. Therefore, if a string occurs multiple times, we should count it each time it occurs.
You are given a binary string s. Your task is to determine the number of substrings in s that contain exactly k characters "1".
Input Format
The first line contains an integer k.
The second line contains a non-empty binary string s.
Output Format
Print a single number - the count of substrings in the given string that contain exactly k characters "1".
Example
Input
1
1010
Output
6
Constraints
0 ≤ k ≤ 10^6
The length of s is at most 10^6 characters.
Please avoid using the %lld specifier for 64-bit integers in C++. It is recommended to use the cin, cout streams or the %I64d specifier.
Loading...
View Submissions
Console