Minimum Recolors To Get K Consecutive Black Blocks

---

Intuition

This problem reduces to the following question: Given a window of size k, find how many are not black in that window. Then, slide this window until you find the minimum.

Complexity

Runtime

$O(N)$

Space

$O(1)$

Code

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        b_c = 0
        res = inf
 
        j = 0
        for i in range(len(blocks)):
            if blocks[i] == "B":
                b_c += 1
 
            # If you are at a window of size k
            if i + 1 >= k:
                res = min(res, k - b_c) 
 
                if blocks[j] == "B":
                    b_c -= 1
                j += 1
        
        return res

Cards

START Basic Front: Minimum Recolors To Get K Consecutive Black Blocks Back: Find how many are not black in a window of size k END

---

References

• Minimum Recolors To Get K Consecutive Black Blocks