Minimum White Tiles After Covering With Carpets
HardUpdated: Aug 2, 2025
Practice on:
Problem
You are given a 0-indexed binary string floor, which represents the colors of tiles on a floor:
floor[i] = '0'denotes that theithtile of the floor is colored black.- On the other hand,
floor[i] = '1'denotes that theithtile 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 theminimum number of white tiles still visible.
Examples
Example 1
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
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 <= 1000floor[i]is either'0'or'1'.1 <= numCarpets <= 1000
Solution
Method 1 – Dynamic Programming (Top-Down)
Intuition
We want to minimize the number of visible white tiles by optimally placing carpets. At each tile, we can either cover it with a carpet (if we have carpets left) or leave it uncovered. Using DP, we can recursively decide for each position and number of carpets left, and memoize the result.
Approach
- Define a DP function
dp(i, k)for the minimum white tiles from positioniwithkcarpets left. - At each position, either:
- Place a carpet (if k > 0): move to
i + carpetLenand use one carpet. - Don't place a carpet: if tile is white, add 1 and move to
i + 1.
- Place a carpet (if k > 0): move to
- Use memoization to avoid recomputation.
- Start from position 0 with all carpets available.
- Return the minimum value.
Code
C++
class Solution {
public:
int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
int n = floor.size();
vector<vector<int>> memo(n+1, vector<int>(numCarpets+1, -1));
function<int(int,int)> dp = [&](int i, int k) {
if (i >= n) return 0;
if (memo[i][k] != -1) return memo[i][k];
int res = (floor[i] == '1' ? 1 : 0) + dp(i+1, k);
if (k > 0) res = min(res, dp(i+carpetLen, k-1));
return memo[i][k] = res;
};
return dp(0, numCarpets);
}
};
Go
func MinimumWhiteTiles(floor string, numCarpets, carpetLen int) int {
n := len(floor)
memo := make([][]int, n+1)
for i := range memo {
memo[i] = make([]int, numCarpets+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
var dp func(i, k int) int
dp = func(i, k int) int {
if i >= n {
return 0
}
if memo[i][k] != -1 {
return memo[i][k]
}
res := 0
if floor[i] == '1' {
res = 1
}
res += dp(i+1, k)
if k > 0 {
alt := dp(i+carpetLen, k-1)
if alt < res {
res = alt
}
}
memo[i][k] = res
return res
}
return dp(0, numCarpets)
}
Java
class Solution {
public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
int n = floor.length();
int[][] memo = new int[n+1][numCarpets+1];
for (int[] row : memo) Arrays.fill(row, -1);
return dp(0, numCarpets, floor, carpetLen, memo);
}
private int dp(int i, int k, String floor, int carpetLen, int[][] memo) {
if (i >= floor.length()) return 0;
if (memo[i][k] != -1) return memo[i][k];
int res = (floor.charAt(i) == '1' ? 1 : 0) + dp(i+1, k, floor, carpetLen, memo);
if (k > 0) res = Math.min(res, dp(i+carpetLen, k-1, floor, carpetLen, memo));
return memo[i][k] = res;
}
}
Kotlin
class Solution {
fun minimumWhiteTiles(floor: String, numCarpets: Int, carpetLen: Int): Int {
val n = floor.length
val memo = Array(n+1) { IntArray(numCarpets+1) { -1 } }
fun dp(i: Int, k: Int): Int {
if (i >= n) return 0
if (memo[i][k] != -1) return memo[i][k]
var res = if (floor[i] == '1') 1 else 0
res += dp(i+1, k)
if (k > 0) res = minOf(res, dp(i+carpetLen, k-1))
memo[i][k] = res
return res
}
return dp(0, numCarpets)
}
}
Python
from typing import List
class Solution:
def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
n = len(floor)
memo = [[-1] * (numCarpets + 1) for _ in range(n + 1)]
def dp(i: int, k: int) -> int:
if i >= n:
return 0
if memo[i][k] != -1:
return memo[i][k]
res = (floor[i] == '1') + dp(i + 1, k)
if k > 0:
res = min(res, dp(i + carpetLen, k - 1))
memo[i][k] = res
return res
return dp(0, numCarpets)
Rust
impl Solution {
pub fn minimum_white_tiles(floor: String, num_carpet: i32, carpet_len: i32) -> i32 {
let n = floor.len();
let floor_bytes = floor.as_bytes();
let mut memo = vec![vec![-1; (num_carpet+1) as usize]; n+1];
fn dp(i: usize, k: i32, n: usize, carpet_len: i32, floor: &[u8], memo: &mut Vec<Vec<i32>>) -> i32 {
if i >= n { return 0; }
if memo[i][k as usize] != -1 { return memo[i][k as usize]; }
let mut res = if floor[i] == b'1' { 1 } else { 0 } + dp(i+1, k, n, carpet_len, floor, memo);
if k > 0 {
res = res.min(dp(i + carpet_len as usize, k - 1, n, carpet_len, floor, memo));
}
memo[i][k as usize] = res;
res
}
dp(0, num_carpet, n, carpet_len, floor_bytes, &mut memo)
}
}
TypeScript
class Solution {
minimumWhiteTiles(floor: string, numCarpets: number, carpetLen: number): number {
const n = floor.length;
const memo: number[][] = Array.from({length: n+1}, () => Array(numCarpets+1).fill(-1));
function dp(i: number, k: number): number {
if (i >= n) return 0;
if (memo[i][k] !== -1) return memo[i][k];
let res = (floor[i] === '1' ? 1 : 0) + dp(i+1, k);
if (k > 0) res = Math.min(res, dp(i+carpetLen, k-1));
memo[i][k] = res;
return res;
}
return dp(0, numCarpets);
}
}
Complexity
- ⏰ Time complexity:
O(n * k)— Each state (position, carpets left) is computed once, and for each state we do O(1) work. - 🧺 Space complexity:
O(n * k)— The memoization table stores results for each state.