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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum White Tiles After Covering With Carpets

Difficulty: Hard

Problem Description

You are given a 0-indexed binary string floor, which represents the colors of tiles on a floor. Each tile can be either black ('0') or white ('1'). You are also given numCarpets and carpetLen. Your task is to cover the tiles with the given carpets such that the number of white tiles still visible is minimized. Carpets may overlap one another. Return the minimum number of white tiles still visible.

Key Insights

  • Each carpet can cover carpetLen consecutive tiles, allowing for overlapping coverage.
  • The goal is to strategically place the carpets to maximize coverage of white tiles ('1').
  • A dynamic programming approach can be employed to keep track of the minimum white tiles visible as carpets are placed.

Space and Time Complexity

Time Complexity: O(n * numCarpets), where n is the length of the floor string.
Space Complexity: O(numCarpets), for storing the minimum visible white tiles at each step.

Solution

To solve this problem, we can use dynamic programming combined with prefix sums. We first calculate a prefix sum array where each index represents the cumulative count of white tiles from the beginning up to that index. This allows us to quickly calculate the number of white tiles in any segment covered by a carpet.

We then define a DP table where dp[i][j] represents the minimum number of white tiles visible after using j carpets on the first i tiles. We initialize the first row of the DP table for zero carpets, which simply reflects the current number of white tiles.

For each subsequent carpet, we determine the best position to place it by checking all possible starting positions and updating the DP table accordingly. Finally, we retrieve the minimum number of white tiles visible from the last row of the DP table.

Code Solutions

def minimumWhiteTiles(floor: str, numCarpets: int, carpetLen: int) -> int:
    n = len(floor)
    prefix_sum = [0] * (n + 1)
    
    # Create a prefix sum of white tiles
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + (1 if floor[i] == '1' else 0)

    # Initialize dp array
    dp = [[float('inf')] * (numCarpets + 1) for _ in range(n + 1)]
    dp[0][0] = 0  # No tiles, no carpets

    for j in range(1, numCarpets + 1):
        for i in range(n + 1):
            # Without using the j-th carpet
            dp[i][j] = dp[i][j - 1]
            # Check for applying the j-th carpet
            for k in range(i - carpetLen, -1, -1):
                dp[i][j] = min(dp[i][j], dp[k][j - 1] + (prefix_sum[i] - prefix_sum[k]))

    return prefix_sum[n] - min(dp[i][numCarpets] for i in range(n + 1))
← Back to All Questions