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 i^th tile of the floor is colored black.
On the other hand, floor[i] = '1' denotes that the i^th 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

Solution 2: Dynamic Programming

Thinking

We have $m$ carpets of length $L$ and want as few visible white tiles as possible. Enumerating every placement is exponential, and both $n$ and $m$ can be $1000$.

A black tile always jumps to the next index. A floor of black tiles is a chain from $0$ to $n$ of length $n$. Python raises RecursionError when $n=1000$.

Skipping a black tile, leaving a white tile, or laying a carpet all read a later index. Laying a carpet also spends one carpet.

Fill from the right. $f[i][j]$ is the fewest visible white tiles from index $i$ with $j$ carpets left, and $f[n][\cdot]=0$. A black tile copies $f[i+1][j]$. With no carpet left the answer is the remaining white count $s[n]-s[i]$. A white tile takes the minimum of leaving it, $1+f[i+1][j]$, and covering it, $f[i+L][j-1]$.

Let $s[i]$ be the number of white tiles in the first $i$ positions of $\textit{floor}$. Let $f[i][j]$ be the fewest white tiles left visible from index $i$ with $j$ carpets remaining. The answer is $f[0][\textit{numCarpets}]$. Set $f[n][j] = 0$, which means every tile has already been passed.

Fill $i$ from $n - 1$ down to $0$ and $j$ from $0$ through $m$:

If $\textit{floor}[i] = 0$, the tile is black and costs no carpet, so $f[i][j] = f[i + 1][j]$.
If $j = 0$, no carpet remains, so $f[i][j] = s[n] - s[i]$.
Otherwise the tile is white. Leaving it visible costs $1 + f[i + 1][j]$. Laying a carpet of length $L$ jumps to index $i + L$ and leaves $j - 1$ carpets. That branch is $f[i + L][j - 1]$ when $i + L \le n$, and $0$ when the jump passes the end of the floor. $f[i][j]$ is the smaller of the two.

The time complexity is $O(n \times m)$, and the space complexity is $O(n \times m)$. Here $n$ and $m$ are the length of $\textit{floor}$ and the value of $\textit{numCarpets}$.

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;
    }
}


// Solution 2
class Solution {
    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {
        int n = floor.length();
        int[] s = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + (floor.charAt(i) == '1' ? 1 : 0);
        }
        int[][] f = new int[n + 1][numCarpets + 1];
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j <= numCarpets; ++j) {
                if (floor.charAt(i) == '0') {
                    f[i][j] = f[i + 1][j];
                } else if (j == 0) {
                    f[i][j] = s[n] - s[i];
                } else {
                    int cover = i + carpetLen <= n ? f[i + carpetLen][j - 1] : 0;
                    f[i][j] = Math.min(1 + f[i + 1][j], cover);
                }
            }
        }
        return f[0][numCarpets];
    }
}

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);
    }
};


// Solution 2
class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
        int n = floor.size();
        vector<int> s(n + 1);
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + (floor[i] == '1');
        }
        vector<vector<int>> f(n + 1, vector<int>(numCarpets + 1));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = 0; j <= numCarpets; ++j) {
                if (floor[i] == '0') {
                    f[i][j] = f[i + 1][j];
                } else if (j == 0) {
                    f[i][j] = s[n] - s[i];
                } else {
                    int cover = i + carpetLen <= n ? f[i + carpetLen][j - 1] : 0;
                    f[i][j] = min(1 + f[i + 1][j], cover);
                }
            }
        }
        return f[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



# Solution 2
class Solution:
    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:
        n = len(floor)
        s = [0] * (n + 1)
        for i, c in enumerate(floor):
            s[i + 1] = s[i] + int(c == "1")
        f = [[0] * (numCarpets + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(numCarpets + 1):
                if floor[i] == "0":
                    f[i][j] = f[i + 1][j]
                elif j == 0:
                    f[i][j] = s[n] - s[i]
                else:
                    cover = f[i + carpetLen][j - 1] if i + carpetLen <= n else 0
                    f[i][j] = min(1 + f[i + 1][j], cover)
        return f[0][numCarpets]

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)
}


// Solution 2
func minimumWhiteTiles(floor string, numCarpets int, carpetLen int) int {
	n := len(floor)
	s := make([]int, n+1)
	for i := 0; i < n; i++ {
		s[i+1] = s[i]
		if floor[i] == '1' {
			s[i+1]++
		}
	}
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, numCarpets+1)
	}
	for i := n - 1; i >= 0; i-- {
		for j := 0; j <= numCarpets; j++ {
			if floor[i] == '0' {
				f[i][j] = f[i+1][j]
			} else if j == 0 {
				f[i][j] = s[n] - s[i]
			} else {
				cover := 0
				if i+carpetLen <= n {
					cover = f[i+carpetLen][j-1]
				}
				f[i][j] = min(1+f[i+1][j], cover)
			}
		}
	}
	return f[0][numCarpets]
}

function minimumWhiteTiles(floor: string, numCarpets: number, carpetLen: number): number {
    const n = floor.length;
    const f: number[][] = Array.from({ length: n }, () => Array(numCarpets + 1).fill(-1));
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + (floor[i] === '1' ? 1 : 0);
    }
    const dfs = (i: number, j: number): number => {
        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);
        }
        const ans = Math.min(1 + dfs(i + 1, j), dfs(i + carpetLen, j - 1));
        f[i][j] = ans;
        return ans;
    };
    return dfs(0, numCarpets);
}



// Solution 2
function minimumWhiteTiles(floor: string, numCarpets: number, carpetLen: number): number {
    const n = floor.length;
    const s: number[] = Array(n + 1).fill(0);
    for (let i = 0; i < n; ++i) {
        s[i + 1] = s[i] + (floor[i] === '1' ? 1 : 0);
    }
    const f: number[][] = Array.from({ length: n + 1 }, () => Array(numCarpets + 1).fill(0));
    for (let i = n - 1; i >= 0; --i) {
        for (let j = 0; j <= numCarpets; ++j) {
            if (floor[i] === '0') {
                f[i][j] = f[i + 1][j];
            } else if (j === 0) {
                f[i][j] = s[n] - s[i];
            } else {
                const cover = i + carpetLen <= n ? f[i + carpetLen][j - 1] : 0;
                f[i][j] = Math.min(1 + f[i + 1][j], cover);
            }
        }
    }
    return f[0][numCarpets];
}

impl Solution {
    pub fn minimum_white_tiles(floor: String, num_carpets: i32, carpet_len: i32) -> i32 {
        let n = floor.len();
        let a: Vec<u8> = floor.bytes().collect();
        let m = num_carpets as usize;
        let k = carpet_len as usize;

        let mut s = vec![0i32; n + 1];
        for i in 0..n {
            s[i + 1] = s[i] + if a[i] == b'1' { 1 } else { 0 };
        }

        let mut f = vec![vec![-1; m + 1]; n];

        fn dfs(
            i: usize,
            j: usize,
            n: usize,
            k: usize,
            s: &Vec<i32>,
            f: &mut Vec<Vec<i32>>,
            a: &Vec<u8>,
        ) -> i32 {
            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] {
                let v = dfs(i + 1, j, n, k, s, f, a);
                f[i][j] = v;
                return v;
            }

            let t1 = 1 + dfs(i + 1, j, n, k, s, f, a);
            let ni = i + k;
            let t2 = dfs(ni, j - 1, n, k, s, f, a);

            let t = t1.min(t2);
            f[i][j] = t;
            t
        }

        dfs(0, m, n, k, &s, &mut f, &a)
    }
}



// Solution 2
impl Solution {
    pub fn minimum_white_tiles(floor: String, num_carpets: i32, carpet_len: i32) -> i32 {
        let n = floor.len();
        let a: Vec<u8> = floor.bytes().collect();
        let m = num_carpets as usize;
        let k = carpet_len as usize;
        let mut s = vec![0i32; n + 1];
        for i in 0..n {
            s[i + 1] = s[i] + if a[i] == b'1' { 1 } else { 0 };
        }
        let mut f = vec![vec![0i32; m + 1]; n + 1];
        for i in (0..n).rev() {
            for j in 0..=m {
                if a[i] == b'0' {
                    f[i][j] = f[i + 1][j];
                } else if j == 0 {
                    f[i][j] = s[n] - s[i];
                } else {
                    let cover = if i + k <= n { f[i + k][j - 1] } else { 0 };
                    f[i][j] = (1 + f[i + 1][j]).min(cover);
                }
            }
        }
        f[0][m]
    }
}

2209 - Minimum White Tiles After Covering With Carpets

2209. Minimum White Tiles After Covering With Carpets

Description

Solutions

Solution 2: Dynamic Programming

All Problems

All Solutions

Welcome to Subscribe On Youtube

2209. Minimum White Tiles After Covering With Carpets

Description

Solutions

Solution 2: Dynamic Programming

All Problems

All Solutions