Minimum White Tiles After Covering With Carpets

Minimum White Tiles After Covering With Carpets

What is this problem about?

The Minimum White Tiles After Covering With Carpets problem gives you a binary string of floor tiles (1 = white, 0 = black) and a set of carpets, each of a fixed length. You can place each carpet anywhere on the floor to cover tiles. Find the minimum number of white tiles still visible after optimally placing all carpets. This hard Minimum White Tiles After Covering With Carpets coding problem uses prefix sums and dynamic programming to determine optimal carpet placements.

Why is this asked in interviews?

Google asks this because it requires combining prefix sums (to quickly compute the number of white tiles in a range) with DP (to decide where to place each carpet optimally). The string, dynamic programming, and prefix sum interview pattern is at the core, and the problem tests whether candidates can design a DP state that naturally incorporates carpet coverage decisions.

Algorithmic pattern used

DP with prefix sums. Define dp[i][j] = minimum white tiles visible in the first i tiles using exactly j carpets. Precompute prefix sums of white tiles prefixWhite[i]. For each position i and number of carpets j:

• Don't place carpet ending at i: dp[i][j] = dp[i-1][j] + (floor[i-1] == '1').
• Place carpet ending at position i: dp[i][j] = dp[max(0, i - carpetLen)][j-1] (carpet covers positions [i-carpetLen+1, i]).

Take minimum of both options.

Example explanation

Floor: "10110101", carpetLen = 2, numCarpets = 2. prefixWhite = [0,1,1,2,3,3,4,4,5].

• Place carpet at positions [2,3] covering "11" (2 white tiles) and at [5,6] covering "10" (1 white tile). Visible whites from remaining = 5 - 3 = 2.
• DP explores all placements and finds minimum remaining white tiles.

Common mistakes candidates make

• Not using prefix sums and recomputing white tile counts from scratch (O(n²) per DP cell).
• DP state confusion: placing carpet "at" position vs "ending at" position.
• Not taking the max(0, ...) when carpet extends before the start of the floor.
• Off-by-one between 0-indexed array and 1-indexed DP.

Interview preparation tip

DP problems with "place K objects to minimize/maximize" follow a standard pattern: state captures position and objects used, transitions cover "place here" and "don't place here." Prefix sums are the crucial companion — always precompute them before writing the DP. If the DP requires a range query (like "how many whites in positions [l,r]?"), prefix sums give O(1) answers. Practice DP-with-prefix-sum problems like "minimum cost painting" and "interval coverage optimization" to build this combined skillset.