Minimum Recolors to Get K Consecutive Black Blocks — LeetCode 2379 Python Solution

The problem

You are given a 0-indexed string blocks of length n, where blocks[i] is either 'W' or 'B', representing the color of the ith block. The characters 'W' and 'B' denote the colors white and black, respectively.

Example

Input

blocks = "WBBWWBBWBW", k = 7

Output

3

Explanation

One way to achieve 7 consecutive black blocks is to recolor the 0th, 3rd, and 4th blocks

Python solution

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        ans = cnt = blocks[:k].count('W')
        for i in range(k, len(blocks)):
            cnt += blocks[i] == 'W'
            cnt -= blocks[i - k] == 'W'
            ans = min(ans, cnt)
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2379. Minimum Recolors to Get K Consecutive Black Blocks is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems