Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2209.html

2209. Minimum White Tiles After Covering With Carpets (Hard)

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

Companies:
Google

Related Topics:
String, Dynamic Programming, Prefix Sum

Similar Questions:

Solution 1. Fixed-length Sliding Window + DP

Intuition:

  1. Use a sliding window of length carpetLen to compute a cover array where cover[i] is the number of white tiles covered by a carpet placed ending at floor[i].
  2. Use DP to calculate the maximum coverable white tiles using numCarpets carpets.

Algorithm:

Fixed-length Sliding Window:

Keep a rolling sum white as the number of white tiles within the sliding window.

For each i in range [0, N), we:

  • increment white if s[i] == '1'
  • decrement white if s[i - len] == '1'
  • Set cover[i] = white.

DP:

Let dp[i][j + 1] be the maximum number of coverable white tiles where 1 <= i <= numCarpet is number of carpets used and 0 <= j < N is the last index where we can place carpet.

All dp values are initialized as 0s.

For each dp[i][j + 1], we have two options:

  1. Don’t place carpet at index j. dp[i][j+1] = dp[i][j]
  2. Place carpet ending at index j covering cover[j] white tiles. And we can place i-1 carpets at or before j-carpetLen. So, dp[i][j+1] = dp[i-1][j-carpetLen+1] + cover[j].
dp[i][j + 1] = max(
                    dp[i][j],                                                                   // don't place carpet at index `j`
                    (j - carpetLen + 1 >= 0 ? dp[i - 1][j - carpetLen + 1] : 0) + cover[j]      // place carpet at index `j`
                  )

dp[numCarpet][N] is the maximum number of white titles coverable. The answer is the number of total white tiles minus dp[numCarpet][N].

// OJ: https://leetcode.com/problems/minimum-white-tiles-after-covering-with-carpets/
// Time: O(N * numCarpet)
// Space: O(N * numCarpet)
class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpet, int carpetLen) {
        int N = floor.size(), sum = 0;
        vector<int> cover(N);
        for (int i = 0, white = 0; i < N; ++i) {
            sum += floor[i] - '0';
            white += floor[i] - '0';
            if (i - carpetLen >= 0) white -= floor[i - carpetLen] - '0'; 
            cover[i] = white;
        }
        vector<vector<int>> dp(numCarpet + 1, vector<int>(N + 1));
        for (int i = 1; i <= numCarpet; ++i) {
            for (int j = 0; j < N; ++j) {
                dp[i][j + 1] = max(dp[i][j], (j - carpetLen + 1 >= 0 ? dp[i - 1][j - carpetLen + 1] : 0) + cover[j]);
            }
        }
        return sum - dp[numCarpet][N];
    }
};

We can reduce the space complexity to O(N) by using rolling arrays.

// OJ: https://leetcode.com/problems/minimum-white-tiles-after-covering-with-carpets/
// Time: O(N * numCarpet)
// Space: O(N)
class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpet, int carpetLen) {
        int N = floor.size(), sum = 0;
        vector<int> cover(N);
        for (int i = 0, white = 0; i < N; ++i) {
            sum += floor[i] - '0';
            white += floor[i] - '0';
            if (i - carpetLen >= 0) white -= floor[i - carpetLen] - '0'; 
            cover[i] = white;
        }
        vector<int> dp(N + 1);
        for (int i = 1; i <= numCarpet; ++i) {
            vector<int> next(N + 1);
            for (int j = 0; j < N; ++j) {
                next[j + 1] = max(next[j], (j - carpetLen + 1 >= 0 ? dp[j - carpetLen + 1] : 0) + cover[j]);
            }
            swap(dp, next);
        }
        return sum - dp[N];
    }
};

Disucss

https://leetcode.com/problems/minimum-white-tiles-after-covering-with-carpets/discuss/1863879

All Problems

All Solutions