#2209

Minimum White Tiles After Covering With Carpets

master · 1745 · lc hard +32 · verified · 38.6% accepted · 523 likes · top 18%

Description

You are given a 0-indexed binary string floor representing tile colors:

- floor[i] = '0' means tile i is black.

- floor[i] = '1' means tile i is white.

You have numCarpets identical black carpets, each covering carpetLen consecutive tiles. Carpets can overlap. Place the carpets to minimize the number of visible white tiles.

Return the minimum number of white tiles still visible.

Example 1:

Input: floor = "10110101", numCarpets = 2, carpetLen = 2

Output: 2

Explanation:

The figure above shows one way of covering the tiles with the carpets such that only 2 white tiles are visible.

No other way of covering the tiles with the carpets can leave less than 2 white tiles visible.

Example 2:

Input: floor = "11111", numCarpets = 2, carpetLen = 3

Output: 0

Explanation:

The figure above shows one way of covering the tiles with the carpets such that no white tiles are visible.

Note that the carpets are able to overlap one another.

Code

1

2

3

class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:

class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int: