We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum White Tiles After Covering With Carpets

Number: 2311

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a binary string representing a floor (with '1' for white and '0' for black tiles), and a specified number of carpets each of a fixed length, the task is to cover parts of the floor using these carpets so that the number of white tiles still visible is minimized. Carpets can overlap, meaning that they can cover any part of the floor independently.

Key Insights

  • Since carpets can overlap, applying a carpet covers a contiguous segment of tiles and avoids double-counting uncovered white tiles.
  • Dynamic programming is a natural approach: at each tile, decide whether to cover starting at that tile using a carpet (if available) or to leave the current white tile and move on.
  • A recursive (or bottom-up) DP formulation can be used where the state is defined by the current index in the floor string and the number of carpets remaining.
  • Precomputing a prefix sum of white tiles can be useful in alternate solutions but in our DP the decision is local so we cover a block in one move.
  • The overlapping property implies that it is never harmful to cover a region even if some part was already covered by another carpet.

Space and Time Complexity

Time Complexity: O(n * numCarpets), where n is the length of the floor string. Space Complexity: O(n * numCarpets) if a 2D DP table is used; optimized approaches can reduce space further.

Solution

We use a recursive dynamic programming approach with memoization. Define a function dp(i, carpetsLeft) that returns the minimum number of white tiles visible from index i to the end given that we have "carpetsLeft" carpets remaining. For each state, there are two options:

  1. Do not use a carpet at the current index: In this case, if the current tile is white, add 1 to the uncovered count, and continue to the next tile.
  2. Use a carpet (if available) starting from the current index: This will cover the next carpetLen tiles (i.e. move to index i + carpetLen) with no additional cost for covered whites. The answer is dp(0, numCarpets).

We also include all necessary line-by-line comments in the code solutions below to explain the thought process.

Code Solutions

# Python implementation for Minimum White Tiles After Covering With Carpets
def minimumWhiteTiles(floor: str, numCarpets: int, carpetLen: int) -> int:
    n = len(floor)
    # Use memoization to cache results from (index, carpetsLeft)
    memo = {}

    def dp(idx, carpetsLeft):
        # Base case: if we reached the end of the floor, no white tiles remain uncovered
        if idx >= n:
            return 0
        # Check if the result is already computed
        if (idx, carpetsLeft) in memo:
            return memo[(idx, carpetsLeft)]
        
        # Option 1: Do not use a carpet at current index - add white cost if current is white.
        # Then move one tile ahead.
        cost_without_carpet = (1 if floor[idx] == '1' else 0) + dp(idx + 1, carpetsLeft)
        
        # Option 2: Use a carpet if available - skip carpetLen tiles.
        cost_with_carpet = float('inf')
        if carpetsLeft > 0:
            cost_with_carpet = dp(idx + carpetLen, carpetsLeft - 1)
        
        # Store the best option
        best = min(cost_without_carpet, cost_with_carpet)
        memo[(idx, carpetsLeft)] = best
        return best

    return dp(0, numCarpets)

# Example test
print(minimumWhiteTiles("10110101", 2, 2))  # Expected output: 2
← Back to All Questions