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 theminimum number of white tiles still visible.

Examples

Example 1

1
2
3
4
5
6
7
8


![](https://assets.leetcode.com/uploads/2022/02/10/ex1-1.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

1
2
3
4
5
6
7
8


![](https://assets.leetcode.com/uploads/2022/02/10/ex2.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

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

  1. Define a DP function dp(i, k) for the minimum white tiles from position i with k carpets left.
  2. At each position, either:
    • Place a carpet (if k > 0): move to i + carpetLen and use one carpet.
    • Don’t place a carpet: if tile is white, add 1 and move to i + 1.
  3. Use memoization to avoid recomputation.
  4. Start from position 0 with all carpets available.
  5. Return the minimum value.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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.