Few Zeros or Few Ones

Easy

You are given a string bits made of 0 and 1 characters and an integer cap. Call a substring lopsided if it has at most cap zeros **or** at most cap ones (either condition is enough). Return the number of lopsided substrings. A substring is a contiguous piece of the string; equal substrings at different positions are counted separately.

Example 1

bits="0110", cap=1 → 9

The string has 10 substrings. Only the whole "0110" fails, with two zeros and two ones. The answer is 9.

Example 2

bits="0000", cap=1 → 10

No substring contains a one, so all 10 qualify.

Example 3

bits="010101", cap=2 → 20

Any substring of length up to 5 has at most two zeros or at most two ones, while the full string has three of each. The answer is 21 − 1 = 20.

Constraints

1 ≤ len(bits) ≤ 50
1 ≤ cap ≤ len(bits)
Every character of bits is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Sliding Window

Similar problems

Both Cases Stretch Easy Triples Without Repeats Easy Digit Windows That Divide Easy Repaint for a Dark Stretch Easy Each Letter At Most Twice Easy

Input

bits="0110", cap=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 107 tests on the server, hidden ones included.