Minimum White Tiles After Covering With Carpets — Hard Problem & Solution

floor[i] is '1' for a white tile and '0' for a black one. You have numCarpets carpets, each covering exactly carpetLen consecutive tiles.

Difficulty: Hard
Topics: Strings, Dynamic Programming, Prefix Sum
Asked at: Amazon, Google, Uber
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

floor[i] is '1' for a white tile and '0' for a black one. You have numCarpets carpets, each covering exactly carpetLen consecutive tiles. Carpets may overlap and must not hang off either end.

Return the minimum number of white tiles still visible after placing the carpets.

Example 1

Input: floor = "10110101", numCarpets = 2, carpetLen = 2
Output: 2

Example 2

Input: floor = "11111", numCarpets = 2, carpetLen = 3
Output: 0
Explanation: Two carpets of length 3 cover all five tiles.

Example 3

Input: floor = "10", numCarpets = 1, carpetLen = 1
Output: 0

Constraints

1 <= carpetLen <= floor.length <= 1000
floor[i] is '0' or '1'
1 <= numCarpets <= 1000

How to solve Minimum White Tiles After Covering With Carpets

A two-dimensional DP over prefix length and carpets used. At each prefix end the only decision is whether a carpet finishes there, which makes the transition a simple two-way minimum.

Approach

dp[0][i] is the number of white tiles in the first i tiles — no carpets available.
For j >= 1, either skip the tile (dp[j][i-1] + isWhite(i)) or end a carpet at i (dp[j-1][i - carpetLen], or 0 if the carpet covers the whole prefix).
Take the smaller of the two; the answer is dp[numCarpets][n].

Why it works

A carpet placement is fully described by where it ends, so scanning prefix ends enumerates every arrangement. Overlap costs nothing but never helps — the DP naturally avoids it, since a carpet that ends earlier covers at least as much new ground. Letting a carpet 'hang off' the front is handled by the 0 branch, which is correct because a carpet covering the whole remaining prefix leaves nothing visible.

Complexity

Time — O(n · numCarpets)
Space — O(n · numCarpets)

Pitfalls

A carpet may not extend past either end, which is what the i >= carpetLen guard and the 0 fallback encode.
Deciding where carpets start rather than end makes the recurrence look forwards and is harder to write.
numCarpets can exceed what is useful; the DP handles that without special-casing.

Reference solution

Python

def minimumWhiteTiles(floor: str, numCarpets: int, carpetLen: int) -> int:
    n = len(floor)
    dp = [[0] * (n + 1) for _ in range(numCarpets + 1)]
    for i in range(1, n + 1):
        white = 1 if floor[i - 1] == "1" else 0
        dp[0][i] = dp[0][i - 1] + white
        for j in range(1, numCarpets + 1):
            skip = dp[j][i - 1] + white
            cover = dp[j - 1][i - carpetLen] if i >= carpetLen else 0
            dp[j][i] = min(skip, cover)
    return dp[numCarpets][n]

JavaScript

var minimumWhiteTiles = function(floor, numCarpets, carpetLen) {
    var n = floor.length;
    var dp = [];
    for (var a = 0; a <= numCarpets; a++) {
        var row = [];
        for (var b = 0; b <= n; b++) row.push(0);
        dp.push(row);
    }
    for (var i = 1; i <= n; i++) {
        var white = floor.charAt(i - 1) === "1" ? 1 : 0;
        dp[0][i] = dp[0][i - 1] + white;
        for (var j = 1; j <= numCarpets; j++) {
            var skip = dp[j][i - 1] + white;
            var cover = i >= carpetLen ? dp[j - 1][i - carpetLen] : 0;
            dp[j][i] = Math.min(skip, cover);
        }
    }
    return dp[numCarpets][n];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue