# Minimum White Tiles After Covering With Carpets
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-white-tiles-after-covering-with-carpets)
Canonical: https://scaleengineer.com/dsa/problems/minimum-white-tiles-after-covering-with-carpets
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** String
---
## 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**.

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:**

![](https://assets.glich.co/dsa/minimum-white-tiles-after-covering-with-carpets/image0.png) 

**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:**

![](https://assets.glich.co/dsa/minimum-white-tiles-after-covering-with-carpets/image1.png) 

**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.

**Constraints:**

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

# Approaches
## Naive Recursive Approach
This approach involves a straightforward, brute-force recursion to explore all possible ways of placing the carpets. For each tile, we make a decision: either we place a carpet starting at this tile (if we have any left), or we don't. This creates a decision tree that explores all combinations. While simple to understand, its exponential nature makes it impractical for all but the smallest inputs.
**Time:** O(2^n) without memoization. The number of states can be large, and each state branches into two, leading to an exponential number of calls. · **Space:** O(n) for the recursion stack depth in the naive version. O(n * numCarpets) if memoization is added.
**Pros:** Simple to conceptualize and follows the problem's decision-making process directly.
**Cons:** Extremely inefficient due to a massive number of redundant computations for the same subproblems.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The core idea is to define a function that solves the problem for a suffix of the floor. Let's define `solve(index, carpetsLeft)` as the minimum white tiles visible from `index` onwards, with `carpetsLeft` available.

At each `index`, we face a choice:
1.  **Don't place a carpet here:** We move to the next tile `index + 1`, and if the current tile `index` is white, it adds to our count of visible white tiles.
2.  **Place a carpet here:** We use one carpet, which covers the segment `[index, index + carpetLen - 1]`. We then recursively solve for the subproblem starting at `index + carpetLen` with one less carpet.

The function returns the minimum of these two outcomes. The recursion stops when we run out of tiles or carpets.

```java
class Solution {
    private String floor;
    private int n;
    private int carpetLen;
    private int[] suffixWhite;
    private int[][] memo;

    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
        this.floor = floor;
        this.n = floor.length();
        this.carpetLen = carpetLen;
        
        // Using memoization to show the transition to DP, but a pure recursive solution would omit this.
        // A naive solution without memoization would be too slow.
        this.memo = new int[n + 1][numCarpets + 1];
        for (int[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }

        // Precompute suffix sums of white tiles for the base case
        this.suffixWhite = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffixWhite[i] = suffixWhite[i + 1] + (floor.charAt(i) - '0');
        }

        return solve(0, numCarpets);
    }

    // This is the recursive helper. Without memoization, it's a naive approach.
    private int solve(int i, int k) {
        // Base cases
        if (i >= n) {
            return 0;
        }
        if (k == 0) {
            return suffixWhite[i];
        }
        if (memo[i][k] != -1) {
            return memo[i][k];
        }

        // Option 1: Skip tile i
        int skip = (floor.charAt(i) - '0') + solve(i + 1, k);

        // Option 2: Cover starting at tile i
        int cover = solve(i + carpetLen, k - 1);

        return memo[i][k] = Math.min(skip, cover);
    }
}
```
### Algorithm
- Define a recursive function, say `solve(index, carpetsLeft)`, that returns the minimum number of visible white tiles from `index` to the end of the floor, given `carpetsLeft` carpets.
- **Base Cases:**
  - If `index` is beyond the floor's end (`index >= floor.length`), no more tiles are left, so return 0.
  - If `carpetsLeft` is 0, no more carpets can be used. Return the total number of white tiles from `index` to the end. This can be pre-calculated using a suffix sum array for efficiency.
- **Recursive Step:** At `index`, we have two choices:
  1. **Skip:** Don't place a carpet starting at `index`. The cost is 1 if `floor[index]` is white, plus the result of the recursive call for the next tile: `(floor[index] == '1' ? 1 : 0) + solve(index + 1, carpetsLeft)`.
  2. **Cover:** Place a carpet starting at `index`. This covers tiles up to `index + carpetLen - 1`. The cost is the result of the recursive call for the state after the carpet ends: `solve(index + carpetLen, carpetsLeft - 1)`.
- The function returns the minimum of the results from these two choices.

## 2D Dynamic Programming
This approach uses dynamic programming to solve the problem efficiently by avoiding the redundant calculations of the naive recursion. We build a 2D table, `dp[i][j]`, to store the optimal solution for subproblems. The state `dp[i][j]` represents the minimum number of visible white tiles considering the first `i` tiles of the floor and using `j` carpets. By building up the solution from smaller subproblems, we can find the global optimum.
**Time:** O(n * numCarpets) because we iterate through each state of the `dp` table once. · **Space:** O(n * numCarpets) to store the 2D DP table.
**Pros:** Guaranteed to find the optimal solution.; Efficient enough to pass the given constraints with a polynomial time complexity.
**Cons:** The space complexity of O(n * numCarpets) can be large if n and numCarpets are close to their maximum values (1000).
### Explanation
We define `dp[i][j]` as the minimum number of visible white tiles in the prefix `floor[0...i-1]` using `j` carpets. We can fill this table iteratively.

The base cases are straightforward:
- If we use 0 carpets (`j=0`), the number of visible white tiles is simply the total count of white tiles in the prefix.
- If we consider 0 tiles (`i=0`), the number of visible white tiles is 0.

For the general case `dp[i][j]`, we consider the `i`-th tile (at index `i-1`). We have two choices:
1.  We don't place a carpet that ends at `i-1`. In this case, the solution is based on the subproblem for the first `i-1` tiles with `j` carpets, and we add 1 to the count if `floor[i-1]` is white.
2.  We place a carpet ending at `i-1`. This carpet covers `[i-carpetLen, i-1]`. The number of visible tiles is then the solution for the subproblem on the first `i-carpetLen` tiles using `j-1` carpets.

We take the minimum of these two choices.

```java
class Solution {
    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
        int n = floor.length();
        int[][] dp = new int[n + 1][numCarpets + 1];

        // dp[i][j]: min visible white tiles in floor[0...i-1] using j carpets

        for (int i = 1; i <= n; i++) {
            // Base case: j = 0 carpets
            dp[i][0] = dp[i - 1][0] + (floor.charAt(i - 1) - '0');
            
            for (int j = 1; j <= numCarpets; j++) {
                // Option 1: Don't cover tile i-1 with a new carpet.
                int option1 = dp[i - 1][j] + (floor.charAt(i - 1) - '0');
                
                // Option 2: Cover tiles [i-carpetLen, i-1] with a carpet.
                int option2;
                if (i >= carpetLen) {
                    option2 = dp[i - carpetLen][j - 1];
                } else {
                    // If i < carpetLen, we can use one carpet to cover all tiles from 0 to i-1.
                    option2 = 0;
                }
                
                dp[i][j] = Math.min(option1, option2);
            }
        }

        return dp[n][numCarpets];
    }
}
```
### Algorithm
- Create a 2D DP table, `dp[i][j]`, of size `(n+1) x (numCarpets+1)`.
- `dp[i][j]` will store the minimum number of visible white tiles in the prefix `floor[0...i-1]` using `j` carpets.
- **Initialization:**
  - `dp[0][j] = 0` for all `j` (no tiles, no visible white tiles).
  - `dp[i][0]` for `i > 0` is the number of white tiles in `floor[0...i-1]`, as no carpets are used. This is calculated as `dp[i-1][0] + (floor.charAt(i-1) - '0')`.
- **Transition:** Iterate through `i` from 1 to `n` and `j` from 1 to `numCarpets`.
  - For each `dp[i][j]`, we have two choices regarding the tile `i-1`:
    1. **Don't end a carpet at `i-1`:** The number of visible tiles is the result for the prefix `i-1` with `j` carpets, plus one if `floor[i-1]` is white. This is `dp[i-1][j] + (floor.charAt(i-1) - '0')`.
    2. **End a carpet at `i-1`:** This covers the range `[i-carpetLen, i-1]`. The number of visible tiles is determined by the state before this carpet, which is `dp[i-carpetLen][j-1]`. If `i < carpetLen`, we can cover all tiles from `0` to `i-1`, resulting in 0 visible tiles.
  - The recurrence relation is: `dp[i][j] = min(option1, option2)`.
- **Result:** The final answer is `dp[n][numCarpets]`.

## Space-Optimized 1D Dynamic Programming
This is the most optimized approach. It builds upon the 2D DP solution by reducing its space complexity. By analyzing the dependencies in the DP recurrence relation, we notice that to compute the solutions for `j` carpets, we only need the solutions for `j-1` carpets. This means we don't need to store the entire 2D DP table. We can get by with just two 1D arrays: one for the previous state (j-1 carpets) and one for the current state (j carpets). This reduces the space complexity from O(n * numCarpets) to O(n) while keeping the time complexity the same.
**Time:** O(n * numCarpets), as the nested loop structure is preserved. · **Space:** O(n), as we only need two arrays of size `n+1`.
**Pros:** Optimal space complexity, making it very memory-efficient.; Maintains the efficient time complexity of the 2D DP approach.
**Cons:** The implementation can be slightly more complex due to the need to manage and update two separate arrays.
### Explanation
The recurrence relation for the 2D DP is `dp[i][j] = min(dp[i-1][j] + ..., dp[i-carpetLen][j-1])`. When we are calculating the values for `j` carpets, we only need values from the `j-1` column. This suggests we can optimize the space.

We can use two 1D arrays: `prev_dp` to store the results for `j-1` carpets, and `dp` to compute the results for `j` carpets. The loops are structured with the number of carpets `j` on the outside.

```java
class Solution {
    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
        int n = floor.length();
        
        // dp[i] will store min visible tiles in floor[0...i-1] for the current number of carpets
        int[] dp = new int[n + 1];
        // prev_dp[i] will store the results for one fewer carpet
        int[] prev_dp = new int[n + 1];

        // Initialize for 0 carpets
        for (int i = 1; i <= n; i++) {
            prev_dp[i] = prev_dp[i - 1] + (floor.charAt(i - 1) - '0');
        }

        // If no carpets, return the total number of white tiles
        if (numCarpets == 0) {
            return prev_dp[n];
        }

        for (int j = 1; j <= numCarpets; j++) {
            dp[0] = 0; // For an empty prefix, visible tiles are 0
            for (int i = 1; i <= n; i++) {
                // Option 1: Don't cover tile i-1 with a new carpet
                int option1 = dp[i - 1] + (floor.charAt(i - 1) - '0');
                
                // Option 2: Cover tiles [i-carpetLen, i-1] with a carpet
                int option2;
                if (i >= carpetLen) {
                    option2 = prev_dp[i - carpetLen];
                } else {
                    option2 = 0;
                }
                
                dp[i] = Math.min(option1, option2);
            }
            // The current dp becomes the prev_dp for the next iteration.
            // A pointer swap would be more efficient than copying, but this is clear.
            System.arraycopy(dp, 0, prev_dp, 0, n + 1);
        }

        // After the loop, prev_dp holds the result for numCarpets
        return prev_dp[n];
    }
}
```
### Algorithm
- Observe that the calculation of `dp[i][j]` only depends on values from the current column `j` (specifically `dp[i-1][j]`) and the previous column `j-1` (specifically `dp[i-carpetLen][j-1]`).
- This dependency allows us to optimize space. Instead of a 2D table, we can use two 1D arrays: `dp` for the current number of carpets `j`, and `prev_dp` for `j-1` carpets.
- **Initialization:**
  - Create `dp` and `prev_dp` arrays of size `n+1`.
  - Initialize `prev_dp` to represent the case with 0 carpets: `prev_dp[i]` is the count of white tiles in `floor[0...i-1]`.
- **Transition:** Iterate `j` from 1 to `numCarpets`.
  - Inside this loop, iterate `i` from 1 to `n` to calculate `dp[i]`.
  - `dp[i] = min(dp[i-1] + (floor.charAt(i-1)-'0'), (i >= carpetLen ? prev_dp[i-carpetLen] : 0))`.
  - After the inner loop (for `i`) completes, the `dp` array holds the results for `j` carpets. We then update `prev_dp` with the contents of `dp` to prepare for the next iteration of `j`.
- **Result:** After the outer loop finishes, `dp[n]` (or `prev_dp[n]` depending on implementation) will hold the final answer for `numCarpets`.

# Solutions
### Java

```java
class Solution {
private
  int[][] f;
private
  int[] s;
private
  int n;
private
  int k;
public
  int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
    n = floor.length();
    f = new int[n][numCarpets + 1];
    for (var e : f) {
      Arrays.fill(e, -1);
    }
    s = new int[n + 1];
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + (floor.charAt(i) == '1' ? 1 : 0);
    }
    k = carpetLen;
    return dfs(0, numCarpets);
  }
private
  int dfs(int i, int j) {
    if (i >= n) {
      return 0;
    }
    if (j == 0) {
      return s[n] - s[i];
    }
    if (f[i][j] != -1) {
      return f[i][j];
    }
    if (s[i + 1] == s[i]) {
      return dfs(i + 1, j);
    }
    int ans = Math.min(1 + dfs(i + 1, j), dfs(i + k, j - 1));
    f[i][j] = ans;
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: int minimumWhiteTiles ( string floor , int numCarpets , int carpetLen ) { int n = floor . size (); vector < vector < int >> f ( n , vector < int > ( numCarpets + 1 , - 1 )); vector < int > s ( n + 1 ); for ( int i = 0 ; i < n ; ++ i ) { s [ i + 1 ] = s [ i ] + ( floor [ i ] == '1' ); } function < int ( int , int ) > dfs ; dfs = [ & ]( int i , int j ) { if ( i >= n ) return 0 ; if ( j == 0 ) return s [ n ] - s [ i ]; if ( f [ i ][ j ] != - 1 ) return f [ i ][ j ]; if ( s [ i + 1 ] == s [ i ]) return dfs ( i + 1 , j ); int ans = min ( 1 + dfs ( i + 1 , j ), dfs ( i + carpetLen , j - 1 )); f [ i ][ j ] = ans ; return ans ; }; return dfs ( 0 , numCarpets ); } };
```

### Python

```python
class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int: @ cache def dfs(i, j): 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

```