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 <= 1000floor[i] is either '0' or '1'.1 <= numCarpets <= 1000
Solutions
Solution 1: Memoization Search
We design a function 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 dfs(0, numCarpets).
For index i, we discuss the following cases:
- If i \ge n, it means all tiles have been covered, return 0;
- If floor[i] = 0, then we do not need to use a carpet, just skip it, i.e., dfs(i, j) = 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., dfs(i, j) = s[n] - s[i];
- If floor[i] = 1, then we can choose to use a carpet or not, and take the minimum of the two, i.e., dfs(i, j) = min(dfs(i + 1, j), dfs(i + carpetLen, j - 1)).
We use memoization search to solve this problem.
The time complexity is O(n × m), and the space complexity is O(n × m). Here, n and m are the length of the string floor and the value of numCarpets, respectively.
PythonJavaC++GoTypeScriptRust
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(code-box)
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;
}
}(code-box)
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);
}
};(code-box)
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)
}(code-box)
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);
}(code-box)
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)
}
}(code-box)
