Max Consecutive Ones II

You are given a binary string s consisting only of characters '0' and '1', and an integer k. Your task is to determine the maximum number of consecutive 1s that can be obtained in the string by flipping at most k occurrences of the character '0' to '1'.

The problem can be formulated as follows. Given a binary string s and an integer k, find the maximum length L such that there exists a subarray (continuous segment) of s where by flipping at most k zeros to ones, all the characters become 1. In mathematical notation, let L = max(right - left + 1) subject to:

$$ \text{number of zeros in } s[left \ldots right] \le k $$

It is guaranteed that the input will allow a solution that can be computed in linear time.

inputFormat

The input is given via stdin and consists of two lines:

• The first line contains the binary string s.
• The second line contains the integer k.

outputFormat

Output a single integer representing the maximum number of consecutive 1s obtainable after flipping at most k zeros.

The result should be written to stdout.

110100110
3

8