Minimum White Tiles After Covering With Carpets
01 · Problem
A floor is described by a binary string floor, where floor[i] = '0' means tile i is black and floor[i] = '1' means it is white.
You have numCarpets black carpets, each exactly carpetLen tiles long. A carpet covers a contiguous block of tiles. Carpets may overlap each other, and a carpet may hang past the end of the floor. You do not have to use every carpet.
Return the minimum number of white tiles that remain visible (not covered by any carpet).
02 · Examples
floor = "10110101", numCarpets = 2, carpetLen = 2
2
Cover tiles 2-3 and tiles 4-5. The white tiles at indices 0 and 7 remain visible. No placement of two length-2 carpets can hide more white tiles.
floor = "11111", numCarpets = 2, carpetLen = 3
0
Cover tiles 0-2 and tiles 2-4 (the carpets overlap on tile 2). Every tile is covered, so no white tile is visible.
03 · Constraints
- 011 <= carpetLen <= floor.length <= 1000
- 02floor[i] is either '0' or '1'
- 031 <= numCarpets <= 1000
04 · Optimal complexity
- Time
- O(n * numCarpets)
- Space
- O(n * numCarpets)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.