#2209

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum White Tiles After Covering With Carpets

Find the minimum number of white tiles visible after optimally placing carpets using state transition dynamic programming.

string dynamic programming prefix sum

Problem Statement

You are given a binary string representing a floor, where '1' indicates a white tile and '0' indicates a black tile. You have a set number of black carpets, each covering a fixed length of tiles.

Your task is to place all carpets optimally, possibly overlapping, so that the number of visible white tiles is minimized. Return the minimum count of white tiles left uncovered.

Examples

Example 1

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

Output: 2

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

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.

Constraints

1 <= carpetLen <= floor.length <= 1000
floor[i] is either '0' or '1'.
1 <= numCarpets <= 1000

Solution Approach

Dynamic Programming State Definition

Define dp[i][k] as the minimum number of white tiles visible starting from index i with k carpets left. Transition considers either skipping the current tile or placing a carpet of length carpetLen starting at i.

Prefix Sum Optimization

Precompute prefix sums of white tiles to quickly calculate the number of white tiles a carpet would cover. This avoids recalculating sums repeatedly during state transitions and keeps the DP efficient.

Iterative or Recursive Computation

Fill dp either recursively with memoization or iteratively from the end of the floor to the start. Each step chooses the option that leaves the fewest white tiles visible, handling overlaps naturally by state transitions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n numCarpets) where n is the length of floor, since each DP state depends on remaining carpets. Space can be O(n numCarpets) for full DP table, or optimized to O(n) per carpet iteration using rolling arrays. Prefix sum computation adds O(n) time and space but improves efficiency for range calculations.

What Interviewers Usually Probe

Look for correct DP state definition and transitions.
Check handling of overlapping carpets and full coverage scenarios.
Ask if prefix sums can optimize repeated white tile counting.

Common Pitfalls or Variants

Common pitfalls

Forgetting carpets can overlap, leading to incorrect minimum counts.
Not handling edge cases where carpetLen exceeds remaining floor length.
Incorrectly updating DP states when skipping tiles versus placing a carpet.

Follow-up variants

Change to minimize black tiles visible instead of white tiles.
Allow carpets of varying lengths instead of a fixed carpetLen.
Provide multiple floors and require independent minimization for each.

FAQ

What is the main pattern used in Minimum White Tiles After Covering With Carpets?

State transition dynamic programming tracks minimal visible white tiles for each index with remaining carpets.

Can carpets overlap in this problem?

Yes, carpets may overlap, and the DP must account for overlapping ranges correctly.

How do prefix sums help in this problem?

Prefix sums allow fast computation of white tiles covered by a carpet, reducing redundant calculations.

What is the time complexity of this solution?

The time complexity is O(n*numCarpets), where n is the length of the floor string.

Can we optimize space usage in the DP approach?

Yes, by using rolling arrays, space can be reduced to O(n) per carpet iteration instead of O(n*numCarpets).

terminal

Solution

Solution 1: Memoization Search

We design a function $\textit{dfs}(i, j)$ to represent the minimum number of white tiles that are not covered starting from index $i$ using $j$ carpets. The answer is $\textit{dfs}(0, \textit{numCarpets})$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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

Continue Practicing

#2222 number of ways to select buildings #1871 jump game vii #2207 maximize number of subsequences in a string