Flip consecutive zeroes to ones in k operations to have maximum number of ones, find the maximum number of ones

Question

You are given a binary string made of 0 and 1, and a value k which represents number of operations. You can flip consecutive 0s in each operation to 1s. Find the maximum number of 1s after k operations.

For example: input: "00010", k=1 output: 4 explanation: we can convert first three consecutive 0s to 1s in one operation. the result is "11110". answer is 4.

input: "1100101001", k=2 output: 7 explanation: we can convert 0s at indices[2,3] to 1s in first operation and then 0 at index 5 to 1. the result after two operations is 1111111001. answer is 7.

I thought of using sliding window but I am unable to solve using it as we need to form a result with maximum 1s considering the consecutive 0s to be flipped to 1s which can make the result with maximum 1s.

Answer 1

A sliding window approach will work. In order to maximise the number of consecutive 1s, it only makes sense to choose adjacent groups of 0s for conversion to 1s (i.e. without any non-chosen 0s between them), otherwise we spend our k on creating disjoint islands of 1s, which is a waste. So you'd first choose the first k groups of 0s, then unselect the first one of these and append the next one, ...etc, "sliding" through the input, each time checking which one of these options represents the longest result.

Here is an implementation of the sliding window approach written in JavaScript:

function solve(pattern, k) {
    let start = 0; // start index of the "window"
    let size = 0; // Longest result found so far
    for (let end = 0; end < pattern.length; end++) { // Grow window to the right
        if (pattern[end] == "0" && (end == 0 || pattern[end-1] == "1")) {
            // We encounter a first 0 in a group of 0s
            k--; // Adjust the number of 0-groups we are still allowed to consume
            if (k < 0) { // Must give up a group of 0s
                // Shrink window from the left side, dropping one 0-group
                while (pattern[start] == 1) start++;
                while (pattern[start] == 0) start++;
                k++; // ...and allow for one more 0-group at the right
            }
        }
        if (end - start >= size) size = end + 1 - start; // best so far
    }
    return size;
}

let count = solve("1100101001", 2);
console.log(count);