2209. Minimum White Tiles After Covering With Carpets

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

Solution 1: Memoization Search

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(n \times m)\), and the space complexity is \(O(n \times m)\). Here, \(n\) and \(m\) are the length of the string \(\textit{floor}\) and the value of \(\textit{numCarpets}\), respectively.

Python3JavaC++GoTypeScript

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

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;
    }
}

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);
    }
};

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)
}

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);
}

Comments