Festival Lights in a Few Bands

A string of festival bulbs is described by lights, a string of 0 (dark) and 1 (lit). A band is a maximal block of neighbouring lit bulbs. The controller can only drive at most k bands. You may switch any bulbs on or off; each bulb you change costs 1.

Return the smallest number of bulbs to change so that the string has at most k bands. An empty string needs 0 changes.

Examples

Input:  lights = "1101011", k = 1
Output: 2
Explanation: switch on both dark bulbs: "1111111".

Input:  lights = "10101", k = 2
Output: 1
Explanation: for example switch on the second bulb: "11101".

Input:  lights = "0110", k = 0
Output: 2

Constraints

• 0 <= len(lights) <= 2 * 10**4
• 0 <= k <= 50
• Target complexity: O(len(lights) * k). Trying every placement of bands is far too slow.

Goals

• Add a counter dimension (bands used) and a mode bit (lit or dark) to a scan
• Charge a new band only on a dark-to-lit transition
• Recognise why greedily cutting the cheapest bands or gaps is not enough