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.
- 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 <= 1000floor[i] is '0' or '1'1 <= numCarpets <= 1000
Hints for Minimum White Tiles After Covering With Carpets
Hint 1
Decide, for each position from the right end backwards, whether a carpet ends there.
Hint 2
dp[j][i]is the fewest white tiles visible among the firstitiles using at mostjcarpets.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
dp[0][i]is the number of white tiles in the firstitiles — no carpets available.- For
j >= 1, either skip the tile (dp[j][i-1] + isWhite(i)) or end a carpet ati(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 >= carpetLenguard and the 0 fallback encode. - Deciding where carpets start rather than end makes the recurrence look forwards and is harder to write.
numCarpetscan 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