Minimum Recolors to Get K Consecutive Black Blocks

Leetcode Problem:

• Minimum Recolors to Get K Consecutive Black Blocks

Summary

• The problem is to find the minimum number of operations required to have at least k consecutive black blocks in a given string of blocks, where each block is either 'W' or 'B'.

Approach

• The solution uses a sliding window approach to track the number of consecutive black blocks
• It initializes a counter for the number of white blocks within the first k blocks and then slides the window to the right, updating the counter and the minimum number of operations required.

Complexity

• O(n), where n is the length of the string, as each character in the string is processed once.

Explanation

• The solution starts by initializing a counter for the number of white blocks within the first k blocks
• It then slides the window to the right, updating the counter and the minimum number of operations required
• If a white block is encountered within the window, the counter is decremented
• If a black block is encountered within the window, the counter is incremented
• The minimum number of operations required is updated at each step to reflect the current number of white blocks within the window.

Solution Code:

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int w = 0;
        for(int i = 0 ; i < k; i++){
            if(blocks[i] == 'W') w++;
        }
        int ans = w;
        for(int i = k; i < blocks.size(); i++){
            if(blocks[i - k] == 'W'){
                w--;
            }
            if(blocks[i] == 'W'){
                w++;
            }
            ans = min(ans, w);
        }
        return ans;
    }
};