Minimum white tiles after covering with carpets

String Dynamic Programming Prefix Sum

38.6% acceptance

Feb 25, 2026

523

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. On the other hand, 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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_white_tiles(floor: String, num_carpets: i32, carpet_len: i32) -> i32 {
    let s: Vec<i32> = floor.bytes().map(|b| if b == b'1' { 1 } else { 0 }).collect();
    let n = s.len();
    let cl = carpet_len as usize;
    let nc = num_carpets as usize;
    // dp[i][j] = min white tiles visible in s[0..i] using j carpets
    // Recurrence:
    //   no carpet ending here: dp[i][j] = dp[i-1][j] + s[i-1]
    //   carpet ending at i covering [i-cl..i]: dp[i][j] = dp[max(0,i-cl)][j-1]
    let mut dp = vec![vec![i32::MAX / 2; nc + 1]; n + 1];
    for j in 0..=nc { dp[0][j] = 0; }
    for i in 1..=n {
      for j in 0..=nc {
        dp[i][j] = dp[i - 1][j] + s[i - 1];
        if j > 0 {
          let start = if i >= cl { i - cl } else { 0 };
          dp[i][j] = dp[i][j].min(dp[start][j - 1]);
        }
      }
    }
    dp[n][nc]
  }
}