LeetCode-in-Java

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:

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:

Solution

public class Solution {
    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
        int len = floor.length();
        int[][] dp = new int[numCarpets + 1][len + 1];
        int[] prefix = new int[len];
        int tiles = 0;
        int total = 0;
        for (int i = 0; i < len; i++) {
            // calculate total no of Tiles within the Carpet Length Window
            tiles += floor.charAt(i) - '0';
            // start excluding tiles which are not in the Range anymore of the Carpet Length given
            if (i - carpetLen >= 0) {
                tiles -= floor.charAt(i - carpetLen) - '0';
            }
            // the total no of tiles covered within the Carpet Length range for current index
            prefix[i] = tiles;
            total += floor.charAt(i) - '0';
        }
        for (int i = 1; i <= numCarpets; i++) {
            for (int j = 0; j < len; j++) {
                // if we do not wish to cover current Tile
                int doNot = dp[i][j];
                // if we do wish to cover current tile
                int doTake = dp[i - 1][Math.max(0, j - carpetLen + 1)] + prefix[j];
                // we should go back the Carpet length & check for tiles not covered before j -
                // carpet Length distance
                dp[i][j + 1] = Math.max(doTake, doNot);
            }
        }
        return total - dp[numCarpets][len];
    }
}