Minimum White Tiles After Covering With Carpets
Problem
floor is a binary string where '1' is a white tile and '0' is black. You have numCarpets carpets, each covering carpetLen consecutive tiles. Place them (overlaps allowed) to cover as many white tiles as possible. Return the minimum number of white tiles still visible.
floor = "10110101", numCarpets = 2, carpetLen = 22def minimum_white_tiles(floor, numCarpets, carpetLen):
n = len(floor)
# prefix[i] = number of white tiles among floor[0..i-1]
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + (floor[i] == '1')
# dp[i][k] = min visible white among first i tiles using k carpets
dp = [[0] * (numCarpets + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
white = floor[i - 1] == '1'
for k in range(numCarpets + 1):
leave = dp[i - 1][k] + white # tile i-1 left exposed
dp[i][k] = leave
if k > 0:
start = max(0, i - carpetLen) # carpet covers start..i-1
cover = dp[start][k - 1] # those tiles cost 0
dp[i][k] = min(dp[i][k], cover)
return dp[n][numCarpets]function minimumWhiteTiles(floor, numCarpets, carpetLen) {
const n = floor.length;
const dp = Array.from({ length: n + 1 }, () => new Array(numCarpets + 1).fill(0));
for (let i = 1; i <= n; i++) {
const white = floor[i - 1] === '1' ? 1 : 0;
for (let k = 0; k <= numCarpets; k++) {
let res = dp[i - 1][k] + white; // leave tile exposed
if (k > 0) {
const start = Math.max(0, i - carpetLen);
res = Math.min(res, dp[start][k - 1]); // cover with a carpet
}
dp[i][k] = res;
}
}
return dp[n][numCarpets];
}class Solution {
public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
int n = floor.length();
int[][] dp = new int[n + 1][numCarpets + 1];
for (int i = 1; i <= n; i++) {
int white = floor.charAt(i - 1) == '1' ? 1 : 0;
for (int k = 0; k <= numCarpets; k++) {
int res = dp[i - 1][k] + white;
if (k > 0) {
int start = Math.max(0, i - carpetLen);
res = Math.min(res, dp[start][k - 1]);
}
dp[i][k] = res;
}
}
return dp[n][numCarpets];
}
}int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
int n = floor.size();
vector<vector<int>> dp(n + 1, vector<int>(numCarpets + 1, 0));
for (int i = 1; i <= n; i++) {
int white = floor[i - 1] == '1' ? 1 : 0;
for (int k = 0; k <= numCarpets; k++) {
int res = dp[i - 1][k] + white;
if (k > 0) {
int start = max(0, i - carpetLen);
res = min(res, dp[start][k - 1]);
}
dp[i][k] = res;
}
}
return dp[n][numCarpets];
}Explanation
We want to hide as many white tiles as we can with a limited number of carpets, so we minimize the white tiles left visible. Think tile by tile from the left, tracking how many carpets are still in hand.
Let dp[i][k] = the minimum visible white tiles among the first i tiles when k carpets are available. For tile i-1 there are two choices. Leave it exposed: it adds 1 if it is white, plus whatever dp[i-1][k] already costs. Or end a carpet on it: a carpet of length carpetLen covers tiles start..i-1 where start = max(0, i - carpetLen), those tiles cost nothing, and we charge one carpet, giving dp[start][k-1].
We take the smaller of the two. Placing a carpet so it ends exactly at the current tile is enough to capture every useful placement, because shifting a carpet to end earlier never helps cover the tile we are deciding about.
The base row dp[0][k] = 0 (no tiles, nothing visible) seeds everything, and the prefix-white idea is folded directly into the "+white" term, so range white counts are implicit. The answer is dp[n][numCarpets].
Example: floor = "10110101", numCarpets = 2, carpetLen = 2. Two length-2 carpets can hide three of the five white tiles, leaving a minimum of 2 visible.