Rugs Over White Tiles

Hard

A corridor floor is a single row of tiles described by the string floor: '1' is a white tile and '0' is a black one. You have rugs dark rugs, and each covers exactly rug_length consecutive tiles. Rugs may be placed anywhere, overlapping included. Place the rugs so that as few white tiles as possible stay visible, and return that number.

Example 1

floor='1101101', rugs=1, rug_length=3 → 3

There are five white tiles, and any stretch of three tiles covers at most two of them. 3 stay visible.

Example 2

floor='111011', rugs=2, rug_length=2 → 1

Lay the rugs over tiles 1–2 and 4–5; only the white tile 0 remains uncovered.

Example 3

floor='1001', rugs=2, rug_length=1 → 0

Each rug covers one of the two white tiles.

Constraints

1 ≤ rug_length ≤ floor.length ≤ 1000
floor[i] is '0' or '1'
1 ≤ rugs ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

String Dynamic Programming Prefix Sum

Similar problems

Up and Down Orderings Hard Sticky Keys Hard Hop Across Safe Tiles Medium Inspecting Three Buildings Medium Pattern With Dot and Star Hard

Input

floor='1101101', rugs=1, rug_length=3

Expected

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