Watch 5 video solutions for Minimum White Tiles After Covering With Carpets, a hard level problem involving String, Dynamic Programming, Prefix Sum. This walkthrough by Bro Coders has 2,394 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.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 <= 1000Problem Overview: You get a binary string representing a floor where '1' is a white tile and '0' is a black tile. You can place a limited number of carpets, each covering a fixed number of consecutive tiles. The goal is to place these carpets so the number of uncovered white tiles is minimized.
Approach 1: Dynamic Programming (O(n * k) time, O(n * k) space)
This approach models the problem using Dynamic Programming. Let dp[i][j] represent the minimum uncovered white tiles considering the first i tiles with j carpets available. At each tile you either leave it uncovered (add 1 if it's white) or place a carpet ending at that tile and skip the previous carpetLen tiles. The key insight is treating carpet placement as a jump in the DP state. This method guarantees the optimal result and handles overlapping decisions cleanly.
Approach 2: Sliding Window with Prefix Sum (O(n * k) time, O(n) space)
This version uses a prefix sum array to quickly count how many white tiles exist in any segment of length carpetLen. A sliding window evaluates potential carpet placements and determines how many white tiles each placement would cover. Combined with a DP or iterative optimization over carpets used, you repeatedly choose segments that maximize white tiles covered. Prefix sums make each segment query constant time, which keeps the solution efficient even when scanning many possible placements.
Approach 3: Greedy with Precomputation (O(n * k) time, O(n) space)
This strategy precomputes how many white tiles each possible carpet placement can cover. Using this information, you attempt to greedily prioritize segments that remove the most white tiles. Precomputation avoids recalculating counts for every candidate interval. While greedy alone can fail in some overlapping scenarios, combining it with tracking remaining uncovered segments makes it practical for many inputs and simpler to reason about than full DP.
Recommended for interviews: The dynamic programming approach is the expected solution. It clearly models the decision of placing or skipping a carpet and guarantees optimal results. Showing the brute reasoning first and then building the DP transition demonstrates strong problem‑solving skills and familiarity with interval-style DP problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n * k) | O(n * k) | General case where optimal placement decisions must consider overlapping carpet intervals |
| Sliding Window with Prefix Sum | O(n * k) | O(n) | When fast segment queries are needed to evaluate many carpet placements efficiently |
| Greedy with Precomputation | O(n * k) | O(n) | Useful for simpler reasoning when prioritizing segments that cover the most white tiles |