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 <= 1000The key challenge in #2209 Minimum White Tiles After Covering With Carpets is deciding where to place a limited number of carpets so that the number of uncovered white tiles is minimized. Since the floor is represented as a binary string, each position can either contribute to the white tile count or be hidden by a carpet.
A common strategy is to combine Dynamic Programming with Prefix Sum. Prefix sums help quickly compute how many white tiles exist in any substring, allowing efficient evaluation of carpet coverage. The DP state typically represents the minimum uncovered white tiles from a given index while having a certain number of carpets remaining.
At each step, you decide whether to skip the current tile or place a carpet covering the next carpetLen tiles. This decision process builds an optimal solution through overlapping subproblems. With memoization or bottom‑up DP, the algorithm efficiently explores choices without recomputation.
The typical complexity is around O(n × k), where n is the floor length and k is the number of carpets.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Prefix Sum | O(n × k) | O(n × k) |
| Optimized DP (state compression) | O(n × k) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Can you think of a DP solution?
Let DP[i][j] denote the minimum number of white tiles still visible from indices i to floor.length-1 after covering with at most j carpets.
The transition will be whether to put down the carpet at position i (if possible), or not.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like this appear in advanced coding interviews because they test dynamic programming, optimization decisions, and prefix sum techniques. Companies often use similar problems to evaluate problem‑solving and DP reasoning skills.
Prefix sums allow you to quickly compute how many white tiles exist in any segment of the floor. When a carpet covers a range, the algorithm can instantly determine how many white tiles are hidden. This greatly improves efficiency when evaluating DP transitions.
The optimal approach uses dynamic programming combined with prefix sums. DP helps track the minimum uncovered white tiles for each position and remaining carpets, while prefix sums allow fast counting of white tiles in ranges. This avoids recomputation and efficiently evaluates whether to place a carpet or skip a tile.
The solution mainly relies on arrays for prefix sums and a dynamic programming table. Some implementations also use memoization with recursion to store intermediate states. These structures help efficiently track decisions across the floor string.