Welcome to Subscribe On Youtube

2209. Minimum White Tiles After Covering With Carpets

Description

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.

 

Example 1:

Input: floor = "10110101", numCarpets = 2, carpetLen = 2
Output: 2
Explanation: 
The figure above shows one way of covering the tiles with the carpets such that only 2 white tiles are visible.
No other way of covering the tiles with the carpets can leave less than 2 white tiles visible.

Example 2:

Input: floor = "11111", numCarpets = 2, carpetLen = 3
Output: 0
Explanation: 
The figure above shows one way of covering the tiles with the carpets such that no white tiles are visible.
Note that the carpets are able to overlap one another.

 

Constraints:

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

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      private int[][] f;
      private int[] s;
      private int n;
      private int k;
  
      public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
          n = floor.length();
          f = new int[n][numCarpets + 1];
          for (var e : f) {
              Arrays.fill(e, -1);
          }
          s = new int[n + 1];
          for (int i = 0; i < n; ++i) {
              s[i + 1] = s[i] + (floor.charAt(i) == '1' ? 1 : 0);
          }
          k = carpetLen;
          return dfs(0, numCarpets);
      }
  
      private int dfs(int i, int j) {
          if (i >= n) {
              return 0;
          }
          if (j == 0) {
              return s[n] - s[i];
          }
          if (f[i][j] != -1) {
              return f[i][j];
          }
          if (s[i + 1] == s[i]) {
              return dfs(i + 1, j);
          }
          int ans = Math.min(1 + dfs(i + 1, j), dfs(i + k, j - 1));
          f[i][j] = ans;
          return ans;
      }
  }
  

• class Solution {
  public:
      int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
          int n = floor.size();
          vector<vector<int>> f(n, vector<int>(numCarpets + 1, -1));
          vector<int> s(n + 1);
          for (int i = 0; i < n; ++i) {
              s[i + 1] = s[i] + (floor[i] == '1');
          }
          function<int(int, int)> dfs;
          dfs = [&](int i, int j) {
              if (i >= n) return 0;
              if (j == 0) return s[n] - s[i];
              if (f[i][j] != -1) return f[i][j];
              if (s[i + 1] == s[i]) return dfs(i + 1, j);
              int ans = min(1 + dfs(i + 1, j), dfs(i + carpetLen, j - 1));
              f[i][j] = ans;
              return ans;
          };
          return dfs(0, numCarpets);
      }
  };
  

• class Solution:
      def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
          @cache
          def dfs(i, j):
              if i >= n:
                  return 0
              if floor[i] == '0':
                  return dfs(i + 1, j)
              if j == 0:
                  return s[-1] - s[i]
              return min(1 + dfs(i + 1, j), dfs(i + carpetLen, j - 1))
  
          n = len(floor)
          s = [0] * (n + 1)
          for i, c in enumerate(floor):
              s[i + 1] = s[i] + int(c == '1')
          ans = dfs(0, numCarpets)
          dfs.cache_clear()
          return ans
  
  

• func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
  	n := len(floor)
  	f := make([][]int, n)
  	for i := range f {
  		f[i] = make([]int, numCarpets+1)
  		for j := range f[i] {
  			f[i][j] = -1
  		}
  	}
  	s := make([]int, n+1)
  	for i, c := range floor {
  		s[i+1] = s[i] + int(c-'0')
  	}
  	var dfs func(i, j int) int
  	dfs = func(i, j int) int {
  		if i >= n {
  			return 0
  		}
  		if j == 0 {
  			return s[n] - s[i]
  		}
  		if f[i][j] != -1 {
  			return f[i][j]
  		}
  		if s[i+1] == s[i] {
  			return dfs(i+1, j)
  		}
  		ans := min(1+dfs(i+1, j), dfs(i+carpetLen, j-1))
  		f[i][j] = ans
  		return ans
  	}
  	return dfs(0, numCarpets)
  }
  

All Problems

All Solutions