Skip to content

2209. Minimum White Tiles After Covering With Carpets

SourceBiweekly Contest 74 Q4DifficultyHardRating2105

Description

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:

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 <= 1000
  • floor[i] is either '0' or '1'.
  • 1 <= numCarpets <= 1000

Solutions

Thinking

We have \(m\) carpets of length \(L\) and want as few uncovered white tiles as possible. Enumerating placements is exponential; \(n, m \le 10^3\) forbids that. Decisions can be made left to right.

Let \(\textit{dfs}(i, j)\) be the fewest uncovered white tiles from index \(i\) with \(j\) carpets left. A black tile is skipped. With no carpet left, the remainder is the prefix-sum difference \(s[n]-s[i]\). On a white tile we either leave it (\(1 + \textit{dfs}(i+1, j)\)) or cover it (\(\textit{dfs}(i+L, j-1)\)).

There are \(O(nm)\) states and constant work each; memoization yields \(\textit{dfs}(0, m)\).

We design a function \(\textit{dfs}(i, j)\) to represent the minimum number of white tiles that are not covered starting from index \(i\) using \(j\) carpets. The answer is \(\textit{dfs}(0, \textit{numCarpets})\).

For index \(i\), we discuss the following cases:

  • If \(i \ge n\), it means all tiles have been covered, return \(0\);
  • If \(\textit{floor}[i] = 0\), then we do not need to use a carpet, just skip it, i.e., \(\textit{dfs}(i, j) = \textit{dfs}(i + 1, j)\);
  • If \(j = 0\), then we can directly use the prefix sum array \(s\) to calculate the number of remaining uncovered white tiles, i.e., \(\textit{dfs}(i, j) = s[n] - s[i]\);
  • If \(\textit{floor}[i] = 1\), then we can choose to use a carpet or not, and take the minimum of the two, i.e., \(\textit{dfs}(i, j) = \min(\textit{dfs}(i + 1, j), \textit{dfs}(i + \textit{carpetLen}, j - 1))\).

We use memoization search to solve this problem.

The time complexity is \(O(nm)\), and the space complexity is \(O(nm)\), where \(n\) and \(m\) are the length of the string \(\textit{floor}\) and the value of \(\textit{numCarpets}\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            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

 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
34
35
class Solution {
    private Integer[][] f;
    private int[] s;
    private int n;
    private int k;

    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
        n = floor.length();
        f = new Integer[n][numCarpets + 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] != null) {
            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;
    }
}

 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
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');
        }
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            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);
    }
};

 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 int, carpetLen int) int {
    n := len(floor)
    f := make([][]int, n)
    for i := range f {
        f[i] = make([]int, numCarpets+1)
        for j := range f[i] {
            f[i][j] = -1
        }
    }
    s := make([]int, n+1)
    for i, c := range floor {
        s[i+1] = s[i] + int(c-'0')
    }
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        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)
        }
        ans := min(1+dfs(i+1, j), dfs(i+carpetLen, j-1))
        f[i][j] = ans
        return ans
    }
    return dfs(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
function minimumWhiteTiles(floor: string, numCarpets: number, carpetLen: number): number {
    const n = floor.length;
    const f: number[][] = Array.from({ length: n }, () => Array(numCarpets + 1).fill(-1));
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + (floor[i] === '1' ? 1 : 0);
    }
    const dfs = (i: number, j: number): number => {
        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);
        }
        const ans = Math.min(1 + dfs(i + 1, j), dfs(i + carpetLen, j - 1));
        f[i][j] = ans;
        return ans;
    };
    return dfs(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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
impl Solution {
    pub fn minimum_white_tiles(floor: String, num_carpets: i32, carpet_len: i32) -> i32 {
        let n = floor.len();
        let a: Vec<u8> = floor.bytes().collect();
        let m = num_carpets as usize;
        let k = carpet_len as usize;

        let mut s = vec![0i32; n + 1];
        for i in 0..n {
            s[i + 1] = s[i] + if a[i] == b'1' { 1 } else { 0 };
        }

        let mut f = vec![vec![-1; m + 1]; n];

        fn dfs(
            i: usize,
            j: usize,
            n: usize,
            k: usize,
            s: &Vec<i32>,
            f: &mut Vec<Vec<i32>>,
            a: &Vec<u8>,
        ) -> i32 {
            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] {
                let v = dfs(i + 1, j, n, k, s, f, a);
                f[i][j] = v;
                return v;
            }

            let t1 = 1 + dfs(i + 1, j, n, k, s, f, a);
            let ni = i + k;
            let t2 = dfs(ni, j - 1, n, k, s, f, a);

            let t = t1.min(t2);
            f[i][j] = t;
            t
        }

        dfs(0, m, n, k, &s, &mut f, &a)
    }
}

Solution 2: Dynamic Programming

Thinking

We have \(m\) carpets of length \(L\) and want as few visible white tiles as possible. Enumerating every placement is exponential, and both \(n\) and \(m\) can be \(1000\).

A black tile always jumps to the next index. A floor of black tiles is a chain from \(0\) to \(n\) of length \(n\). Python raises RecursionError when \(n=1000\).

Skipping a black tile, leaving a white tile, or laying a carpet all read a later index. Laying a carpet also spends one carpet.

Fill from the right. \(f[i][j]\) is the fewest visible white tiles from index \(i\) with \(j\) carpets left, and \(f[n][\cdot]=0\). A black tile copies \(f[i+1][j]\). With no carpet left the answer is the remaining white count \(s[n]-s[i]\). A white tile takes the minimum of leaving it, \(1+f[i+1][j]\), and covering it, \(f[i+L][j-1]\).

Let \(s[i]\) be the number of white tiles in the first \(i\) positions of \(\textit{floor}\). Let \(f[i][j]\) be the fewest white tiles left visible from index \(i\) with \(j\) carpets remaining. The answer is \(f[0][\textit{numCarpets}]\). Set \(f[n][j] = 0\), which means every tile has already been passed.

Fill \(i\) from \(n - 1\) down to \(0\) and \(j\) from \(0\) through \(m\):

  • If \(\textit{floor}[i] = 0\), the tile is black and costs no carpet, so \(f[i][j] = f[i + 1][j]\).
  • If \(j = 0\), no carpet remains, so \(f[i][j] = s[n] - s[i]\).
  • Otherwise the tile is white. Leaving it visible costs \(1 + f[i + 1][j]\). Laying a carpet of length \(L\) jumps to index \(i + L\) and leaves \(j - 1\) carpets. That branch is \(f[i + L][j - 1]\) when \(i + L \le n\), and \(0\) when the jump passes the end of the floor. \(f[i][j]\) is the smaller of the two.

The time complexity is \(O(nm)\), and the space complexity is \(O(nm)\), where \(n\) and \(m\) are the length of \(\textit{floor}\) and the value of \(\textit{numCarpets}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        n = len(floor)
        s = [0] * (n + 1)
        for i, c in enumerate(floor):
            s[i + 1] = s[i] + int(c == "1")
        f = [[0] * (numCarpets + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(numCarpets + 1):
                if floor[i] == "0":
                    f[i][j] = f[i + 1][j]
                elif j == 0:
                    f[i][j] = s[n] - s[i]
                else:
                    cover = f[i + carpetLen][j - 1] if i + carpetLen <= n else 0
                    f[i][j] = min(1 + f[i + 1][j], cover)
        return f[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
class Solution {
    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
        int n = floor.length();
        int[] s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + (floor.charAt(i) == '1' ? 1 : 0);
        }
        int[][] f = new int[n + 1][numCarpets + 1];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j <= numCarpets; ++j) {
                if (floor.charAt(i) == '0') {
                    f[i][j] = f[i + 1][j];
                } else if (j == 0) {
                    f[i][j] = s[n] - s[i];
                } else {
                    int cover = i + carpetLen <= n ? f[i + carpetLen][j - 1] : 0;
                    f[i][j] = Math.min(1 + f[i + 1][j], cover);
                }
            }
        }
        return f[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
class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
        int n = floor.size();
        vector<int> s(n + 1);
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + (floor[i] == '1');
        }
        vector<vector<int>> f(n + 1, vector<int>(numCarpets + 1));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j <= numCarpets; ++j) {
                if (floor[i] == '0') {
                    f[i][j] = f[i + 1][j];
                } else if (j == 0) {
                    f[i][j] = s[n] - s[i];
                } else {
                    int cover = i + carpetLen <= n ? f[i + carpetLen][j - 1] : 0;
                    f[i][j] = min(1 + f[i + 1][j], cover);
                }
            }
        }
        return f[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
func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
    n := len(floor)
    s := make([]int, n+1)
    for i := 0; i < n; i++ {
        s[i+1] = s[i]
        if floor[i] == '1' {
            s[i+1]++
        }
    }
    f := make([][]int, n+1)
    for i := range f {
        f[i] = make([]int, numCarpets+1)
    }
    for i := n - 1; i >= 0; i-- {
        for j := 0; j <= numCarpets; j++ {
            if floor[i] == '0' {
                f[i][j] = f[i+1][j]
            } else if j == 0 {
                f[i][j] = s[n] - s[i]
            } else {
                cover := 0
                if i+carpetLen <= n {
                    cover = f[i+carpetLen][j-1]
                }
                f[i][j] = min(1+f[i+1][j], cover)
            }
        }
    }
    return f[0][numCarpets]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function minimumWhiteTiles(floor: string, numCarpets: number, carpetLen: number): number {
    const n = floor.length;
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + (floor[i] === '1' ? 1 : 0);
    }
    const f: number[][] = Array.from({ length: n + 1 }, () => Array(numCarpets + 1).fill(0));
    for (let i = n - 1; i >= 0; --i) {
        for (let j = 0; j <= numCarpets; ++j) {
            if (floor[i] === '0') {
                f[i][j] = f[i + 1][j];
            } else if (j === 0) {
                f[i][j] = s[n] - s[i];
            } else {
                const cover = i + carpetLen <= n ? f[i + carpetLen][j - 1] : 0;
                f[i][j] = Math.min(1 + f[i + 1][j], cover);
            }
        }
    }
    return f[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
impl Solution {
    pub fn minimum_white_tiles(floor: String, num_carpets: i32, carpet_len: i32) -> i32 {
        let n = floor.len();
        let a: Vec<u8> = floor.bytes().collect();
        let m = num_carpets as usize;
        let k = carpet_len as usize;
        let mut s = vec![0i32; n + 1];
        for i in 0..n {
            s[i + 1] = s[i] + if a[i] == b'1' { 1 } else { 0 };
        }
        let mut f = vec![vec![0i32; m + 1]; n + 1];
        for i in (0..n).rev() {
            for j in 0..=m {
                if a[i] == b'0' {
                    f[i][j] = f[i + 1][j];
                } else if j == 0 {
                    f[i][j] = s[n] - s[i];
                } else {
                    let cover = if i + k <= n { f[i + k][j - 1] } else { 0 };
                    f[i][j] = (1 + f[i + 1][j]).min(cover);
                }
            }
        }
        f[0][m]
    }
}

Comments