Minimum White Tiles After Covering With Carpets
You are given a 0-indexed binary string floor, which represents the colors of tiles on a floor:
floor[i] = '0'denotes that thei^thtile of the floor is colored black.floor[i] = '1'denotes that thei^thtile of the floor is colored white.
You are also given numCarpets and carpetLen. You have numCarpets black carpets, each of length carpetLen tiles. Cover the tiles with the given carpets such that the number of white tiles still visible is minimum. Carpets may overlap one another.
Return the minimum number of white tiles still visible.
Example 1
Input
floor = "10110101", numCarpets = 2, carpetLen = 2Output
2One way of covering the tiles with the carpets leaves only 2 white tiles visible, and no covering can leave fewer than 2 visible white tiles.
Example 2
Input
floor = "11111", numCarpets = 2, carpetLen = 3Output
0The carpets can overlap, allowing all white tiles to be covered so that no white tiles remain visible.
Constraints
- 1 <= carpetLen <= floor.length <= 1000
- floor[i] is either '0' or '1'.
- 1 <= numCarpets <= 1000