Minimum White Tiles After Covering With Carpets — LeetCode 2209 Python Solution

The problem

You are given a 0-indexed binary string floor, which represents the colors of tiles on a floor: floor[i] = '0' denotes that the ith tile of the floor is colored black. On the other hand, floor[i] = '1' denotes that the ith tile of the floor is colored white.

Example

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.

Python solution

class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= n:
                return 0
            if floor[i] == "0":
                return dfs(i + 1, j)
            if j == 0:
                return s[-1] - s[i]
            return min(1 + dfs(i + 1, j), dfs(i + carpetLen, j - 1))

        n = len(floor)
        s = [0] * (n + 1)
        for i, c in enumerate(floor):
            s[i + 1] = s[i] + int(c == "1")
        ans = dfs(0, numCarpets)
        dfs.cache_clear()
        return ans

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2209. Minimum White Tiles After Covering With Carpets is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems