##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2209.html

# 2209. Minimum White Tiles After Covering With Carpets (Hard)

You are given a **0-indexed binary** string `floor`

, which represents the colors of tiles on a floor:

`floor[i] = '0'`

denotes that the`i`

tile of the floor is colored^{th}**black**.- On the other hand,
`floor[i] = '1'`

denotes that the`i`

tile of the floor is colored^{th}**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:2Explanation: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 = 3Output:0Explanation: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`

**Companies**:

Google

**Related Topics**:

String, Dynamic Programming, Prefix Sum

**Similar Questions**:

## Solution 1. Fixed-length Sliding Window + DP

**Intuition**:

- Use a sliding window of length
`carpetLen`

to compute a`cover`

array where`cover[i]`

is the number of white tiles covered by a carpet placed ending at`floor[i]`

. - Use DP to calculate the maximum coverable white tiles using
`numCarpets`

carpets.

**Algorithm**:

**Fixed-length Sliding Window**:

Keep a rolling sum `white`

as the number of white tiles within the sliding window.

For each `i`

in range `[0, N)`

, we:

- increment
`white`

if`s[i] == '1'`

- decrement
`white`

if`s[i - len] == '1'`

- Set
`cover[i] = white`

.

**DP**:

Let `dp[i][j + 1]`

be the maximum number of coverable white tiles where `1 <= i <= numCarpet`

is number of carpets used and `0 <= j < N`

is the last index where we can place carpet.

All `dp`

values are initialized as `0`

s.

For each `dp[i][j + 1]`

, we have two options:

- Don’t place carpet at index
`j`

.`dp[i][j+1] = dp[i][j]`

- Place carpet ending at index
`j`

covering`cover[j]`

white tiles. And we can place`i-1`

carpets at or before`j-carpetLen`

. So,`dp[i][j+1] = dp[i-1][j-carpetLen+1] + cover[j]`

.

```
dp[i][j + 1] = max(
dp[i][j], // don't place carpet at index `j`
(j - carpetLen + 1 >= 0 ? dp[i - 1][j - carpetLen + 1] : 0) + cover[j] // place carpet at index `j`
)
```

`dp[numCarpet][N]`

is the maximum number of white titles coverable. The answer is the number of total white tiles minus `dp[numCarpet][N]`

.

```
// OJ: https://leetcode.com/problems/minimum-white-tiles-after-covering-with-carpets/
// Time: O(N * numCarpet)
// Space: O(N * numCarpet)
class Solution {
public:
int minimumWhiteTiles(string floor, int numCarpet, int carpetLen) {
int N = floor.size(), sum = 0;
vector<int> cover(N);
for (int i = 0, white = 0; i < N; ++i) {
sum += floor[i] - '0';
white += floor[i] - '0';
if (i - carpetLen >= 0) white -= floor[i - carpetLen] - '0';
cover[i] = white;
}
vector<vector<int>> dp(numCarpet + 1, vector<int>(N + 1));
for (int i = 1; i <= numCarpet; ++i) {
for (int j = 0; j < N; ++j) {
dp[i][j + 1] = max(dp[i][j], (j - carpetLen + 1 >= 0 ? dp[i - 1][j - carpetLen + 1] : 0) + cover[j]);
}
}
return sum - dp[numCarpet][N];
}
};
```

We can reduce the space complexity to `O(N)`

by using rolling arrays.

```
// OJ: https://leetcode.com/problems/minimum-white-tiles-after-covering-with-carpets/
// Time: O(N * numCarpet)
// Space: O(N)
class Solution {
public:
int minimumWhiteTiles(string floor, int numCarpet, int carpetLen) {
int N = floor.size(), sum = 0;
vector<int> cover(N);
for (int i = 0, white = 0; i < N; ++i) {
sum += floor[i] - '0';
white += floor[i] - '0';
if (i - carpetLen >= 0) white -= floor[i - carpetLen] - '0';
cover[i] = white;
}
vector<int> dp(N + 1);
for (int i = 1; i <= numCarpet; ++i) {
vector<int> next(N + 1);
for (int j = 0; j < N; ++j) {
next[j + 1] = max(next[j], (j - carpetLen + 1 >= 0 ? dp[j - carpetLen + 1] : 0) + cover[j]);
}
swap(dp, next);
}
return sum - dp[N];
}
};
```

## Disucss

https://leetcode.com/problems/minimum-white-tiles-after-covering-with-carpets/discuss/1863879