Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

An initial zero needs an odd number of flips, while an initial one needs an even number. With t operations there are exactly t * k flips, and no index can be flipped more than t times. Feasibility can therefore be tested from the counts of zeros and ones without tracking positions.

Approach

Count zeros z and ones o; return zero if z is zero. Try operation counts t from one through the string length. The total flips must be at least z and have the same parity as z, because every additional per-index allowance comes in pairs.

If t is even, zeros can receive at most t - 1 flips and ones at most t, giving upper bound z * (t - 1) + o * t. If t is odd, the bound is z * t + o * (t - 1). Return the first count whose total meets these conditions.

Every same-parity total between the bounds can be distributed into per-index counts. To schedule them, assign each index's flips to consecutive operations in a continuing cyclic traversal of the t operations. Its count is at most t, so it never appears twice in one operation; the total t * k gives exactly k indices per operation.

Searching through n suffices: the allowed flips are binary vectors, and any reachable target is a sum of at most n vectors from a basis of their span. Return -1 if no count qualifies.

class Solution:
    def minOperations(self, s: str, k: int) -> int:
        n = len(s)
        z, o = 0, 0
        for c in s:
            if c == '0':
                z += 1
            else:
                o += 1

        if z == 0:
            return 0

        for op in range(1, n + 1):
            flips = op * k
            if (flips - z) % 2 == 1:
                continue
            if op % 2 == 0:
                if z <= flips <= z * (op - 1) + o * op:
                    return op
            else:
                if z <= flips <= z * op + o * (op - 1):
                    return op

        return -1

Complexity analysis

Let n = s.length. Time: O(n). Auxiliary space: O(1).