Problem Statement
You are given a 0-indexed string blocks of length n, where blocks[i] is either 'W' or 'B', representing the color of the i-th 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.
Constraints
n == blocks.length1 <= n <= 100blocks[i] is either 'W' or 'B'.1 <= k <= n.
Example Inputs and Outputs
-
Example 1:
- Input:
blocks = "WBBWWBBWBW", k = 7
- Output:
3
- Explanation: Recoloring the 0th, 3rd, and 4th blocks results in
"BBBBBBBWBW", which has 7 consecutive black blocks.
-
Example 2:
- Input:
blocks = "WBWBBBW", k = 2
- Output:
0
- Explanation: The input already has 2 consecutive black blocks, so no recoloring is needed.
Brute Force Approach
a. Approach
The brute-force approach involves checking every possible substring of length k in blocks, counting the white blocks in each substring, and tracking the minimum number of white blocks across all possible substrings.
b. Steps
- Loop through each possible substring of length
k.
- Count the white blocks in each substring.
- Track the minimum number of white blocks across all substrings.
- Return the minimum count as it represents the fewest recolors needed.
c. Time & Space Complexity
- Time Complexity: O(n * k), where
n is the length of blocks.
- Space Complexity: O(1), for tracking minimum operations.
d. Code Snippet
e. Dry Run
- Input:
blocks = "WBBWWBBWBW", k = 7
- Check all possible substrings, and find the minimum white blocks needing recoloring, resulting in
3.
Efficient Approach (Sliding Window)
a. Approach
The sliding window approach maintains a window of length k and slides it across blocks. For each new position, we adjust the count of white blocks by checking only the entering and exiting blocks, avoiding redundant counting.
b. Steps
- Initialize a window of length
k and count the white blocks within it.
- Slide the window by one position each time, adjusting the white count by adding the new block's color and removing the exiting block's color.
- Track the minimum number of white blocks required to recolor as the window moves.
- Return this minimum count.
c. Time & Space Complexity
- Time Complexity: O(n), where
n is the length of blocks.
- Space Complexity: O(1).
d. Code Snippet
e. Dry Run
- Input:
blocks = "WBWBBBW", k = 2
- After sliding the window and adjusting white counts, the minimum recolors needed is found to be
0.
Complexity Analysis
a. Brute Force Time & Space Complexity
- Time Complexity: O(n * k)
- Space Complexity: O(1)
b. Optimized Time & Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
Conclusion
The sliding window technique efficiently reduces the need for redundant counting by only adjusting changes in the window. This approach is preferable for beginners to optimize problems involving contiguous substrings or fixed-length subarrays, providing both clarity and efficiency.