# Minimum Recolors to Get K Consecutive Black Blocks
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-recolors-to-get-k-consecutive-black-blocks)
Canonical: https://scaleengineer.com/dsa/problems/minimum-recolors-to-get-k-consecutive-black-blocks
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** String
**Companies:** [HP](https://scaleengineer.com/companies/hp)
---
## 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.

You are also given an integer `k`, which is the desired number of **consecutive** black blocks.

In one operation, you can **recolor** a white block such that it becomes a black block.

Return _the **minimum** number of operations needed such that there is at least **one** occurrence of_ `k` _consecutive black blocks._

**Example 1:**

**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
so that blocks = "BBBBBBBWBW". 
It can be shown that there is no way to achieve 7 consecutive black blocks in less than 3 operations.
Therefore, we return 3.

**Example 2:**

**Input:** blocks = "WBWBBBW", k = 2
**Output:** 0
**Explanation:**
No changes need to be made, since 2 consecutive black blocks already exist.
Therefore, we return 0.

**Constraints:**

* `n == blocks.length`
* `1 <= n <= 100`
* `blocks[i]` is either `'W'` or `'B'`.
* `1 <= k <= n`

# Approaches
## Brute Force with Nested Loops
This approach iterates through all possible consecutive subarrays (windows) of length `k`. For each window, it counts the number of white blocks ('W'), which represents the number of operations needed for that specific window. The minimum count found across all windows is the answer.
**Time:** O(n * k), where `n` is the length of the string and `k` is the window size. The outer loop runs `n - k + 1` times, and for each iteration, the inner loop runs `k` times. · **Space:** O(1), as we only use a few variables to store counts and indices, requiring constant extra space.
**Pros:** It is straightforward to understand and implement.; It correctly solves the problem and is acceptable for small constraints.
**Cons:** This approach is less efficient due to redundant computations. For each window, it recounts all the 'W's, even though adjacent windows have many overlapping characters.
### Explanation
The algorithm works by checking every possible starting position for a sequence of `k` consecutive blocks. An outer loop iterates from the start of the string up to the last possible starting point for a window of size `k` (i.e., `n-k`). For each starting position, an inner loop iterates `k` times to examine the characters within that window. Inside the inner loop, we count the number of 'W' characters. This count is the number of recolors required for the current window. We maintain a variable, `minOperations`, initialized to a large value (or `k`), and update it with the minimum white block count found so far. After checking all possible windows, `minOperations` will hold the minimum number of recolors needed.

```java
class Solution {
    public int minimumRecolors(String blocks, int k) {
        int n = blocks.length();
        int minOperations = k; // At most k operations are needed

        // Iterate through all possible start positions of a window of size k
        for (int i = 0; i <= n - k; i++) {
            int currentWhiteBlocks = 0;
            // Count white blocks in the current window [i, i+k-1]
            for (int j = i; j < i + k; j++) {
                if (blocks.charAt(j) == 'W') {
                    currentWhiteBlocks++;
                }
            }
            // Update the minimum operations needed
            minOperations = Math.min(minOperations, currentWhiteBlocks);
        }
        return minOperations;
    }
}
```
### Algorithm
- Initialize a variable `minOperations` to `k`, which is the maximum possible number of operations.
- Iterate through the string with an index `i` from `0` to `n - k`, where `n` is the length of `blocks`. This index `i` represents the starting position of a window.
- For each starting position `i`, initialize a counter `currentWhiteBlocks` to `0`.
- Create a nested loop with an index `j` from `i` to `i + k - 1` to iterate through the current window of size `k`.
- Inside the inner loop, if the character `blocks.charAt(j)` is 'W', increment `currentWhiteBlocks`.
- After the inner loop finishes, the `currentWhiteBlocks` holds the number of recolors needed for the window starting at `i`.
- Update `minOperations` by taking the minimum of its current value and `currentWhiteBlocks`.
- After the outer loop completes, `minOperations` will contain the minimum number of recolors required across all possible windows. Return `minOperations`.

## Optimized Sliding Window
This approach improves upon the brute-force method by using a sliding window technique. Instead of recounting the white blocks for each window, we maintain a running count. When the window slides one position to the right, we efficiently update the count in constant time by subtracting the character that leaves the window and adding the character that enters.
**Time:** O(n), where `n` is the length of the string. We make a single pass to establish the first window's count (O(k)) and another pass to slide the window (O(n-k)), resulting in a total time complexity of O(n). · **Space:** O(1), as we only use a few variables to store the current count and the minimum count, requiring constant extra space.
**Pros:** Highly efficient with a linear time complexity, making it suitable for larger constraints.; It is the optimal solution for this problem as it requires visiting each character a constant number of times.
**Cons:** While optimal, it can be slightly more complex to conceptualize than a simple nested loop for beginners.
### Explanation
The core idea is to avoid re-computation by reusing the information from the previous window. First, we calculate the number of white blocks in the initial window of size `k` (from index `0` to `k-1`). This count is our initial candidate for the minimum operations. Then, we iterate from index `k` to the end of the string. In each step, we 'slide' the window one position to the right. To update the count of white blocks for the new window, we check the character leaving the window (at `i-k`) and the character entering the window (at `i`). If the leaving character was a 'W', we decrement our white block count. If the entering character is a 'W', we increment the count. After each slide, we compare the current window's white block count with our overall minimum and update it if the current count is smaller. This process continues until the window has traversed the entire string. The final minimum value is the answer.

```java
class Solution {
    public int minimumRecolors(String blocks, int k) {
        int n = blocks.length();
        int whiteBlocksCount = 0;

        // 1. Count white blocks in the first window of size k
        for (int i = 0; i < k; i++) {
            if (blocks.charAt(i) == 'W') {
                whiteBlocksCount++;
            }
        }

        int minOperations = whiteBlocksCount;

        // 2. Slide the window from the first position to the end
        for (int i = k; i < n; i++) {
            // Character entering the window at index i
            if (blocks.charAt(i) == 'W') {
                whiteBlocksCount++;
            }
            // Character leaving the window at index i-k
            if (blocks.charAt(i - k) == 'W') {
                whiteBlocksCount--;
            }
            // Update the minimum operations
            minOperations = Math.min(minOperations, whiteBlocksCount);
        }

        return minOperations;
    }
}
```
### Algorithm
- First, calculate the number of 'W's in the initial window of size `k` (from index `0` to `k-1`). Let's call this `whiteBlocksCount`.
- Initialize `minOperations` to this initial `whiteBlocksCount`.
- Iterate from index `i = k` to `n-1`, effectively sliding the window one position to the right at each step.
- In each iteration, update `whiteBlocksCount` based on the character leaving the window and the character entering it.
  - If the character entering the window (`blocks.charAt(i)`) is 'W', increment `whiteBlocksCount`.
  - If the character that just left the window (`blocks.charAt(i-k)`) was 'W', decrement `whiteBlocksCount`.
- After updating the count, compare it with `minOperations` and update `minOperations = Math.min(minOperations, whiteBlocksCount)`.
- After the loop finishes, `minOperations` will hold the minimum number of 'W's found in any window of size `k`. Return this value.

# Solutions
### Java

```java
class Solution {
public
  int minimumRecolors(String blocks, int k) {
    int cnt = 0;
    for (int i = 0; i < k; ++i) {
      cnt += blocks.charAt(i) == 'W' ? 1 : 0;
    }
    int ans = cnt;
    for (int i = k; i < blocks.length(); ++i) {
      cnt += blocks.charAt(i) == 'W' ? 1 : 0;
      cnt -= blocks.charAt(i - k) == 'W' ? 1 : 0;
      ans = Math.min(ans, cnt);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumRecolors(string blocks, int k) {
    int cnt = count(blocks.begin(), blocks.begin() + k, 'W');
    int ans = cnt;
    for (int i = k; i < blocks.size(); ++i) {
      cnt += blocks[i] == 'W';
      cnt -= blocks[i - k] == 'W';
      ans = min(ans, cnt);
    }
    return ans;
  }
};

```

### Python

```python
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

```