Minimum White Tiles After Covering With Carpets

Hard
896.

Minimum White Tiles After Covering With Carpets

Minimum White Tiles After Covering With Carpets is a hard coding problem on strings, dynamic programming and prefix sum, asked in Amazon, Google and Uber interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} floor
 * @param {number} numCarpets
 * @param {number} carpetLen
 * @return {number}
 */
var minimumWhiteTiles = function(floor, numCarpets, carpetLen) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum White Tiles After Covering With Carpets — Solution

Minimum White Tiles After Covering With Carpets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum White Tiles After Covering With Carpets is a hard coding problem on strings, dynamic programming and prefix sum, asked in Amazon, Google and Uber interviews.

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

Hints for Minimum White Tiles After Covering With Carpets

  1. Hint 1

    Decide, for each position from the right end backwards, whether a carpet ends there.

  2. Hint 2

    dp[j][i] is the fewest white tiles visible among the first i tiles using at most j carpets.

  3. Hint 3

    Either the i-th tile is left uncovered (add it if white) or a carpet covers [i - carpetLen + 1, i].

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

  1. dp[0][i] is the number of white tiles in the first i tiles — no carpets available.
  2. 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).
  3. 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]

Java

public static int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
    int n = floor.length();
    int[][] dp = new int[numCarpets + 1][n + 1];
    for (int i = 1; i <= n; i++) {
        int white = floor.charAt(i - 1) == '1' ? 1 : 0;
        dp[0][i] = dp[0][i - 1] + white;
        for (int j = 1; j <= numCarpets; j++) {
            int skip = dp[j][i - 1] + white;
            int cover = i >= carpetLen ? dp[j - 1][i - carpetLen] : 0;
            dp[j][i] = Math.min(skip, cover);
        }
    }
    return dp[numCarpets][n];
}

C++

int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
    int n = (int) floor.size();
    vector<vector<int>> dp(numCarpets + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++) {
        int white = floor[i - 1] == '1' ? 1 : 0;
        dp[0][i] = dp[0][i - 1] + white;
        for (int j = 1; j <= numCarpets; j++) {
            int skip = dp[j][i - 1] + white;
            int cover = i >= carpetLen ? dp[j - 1][i - carpetLen] : 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming