Understand Minimum Recolors to Get K Consecutive Black Blocks Problem

Problem Name: Minimum Recolors to Get K Consecutive Black Blocks

Problem Description:

Minimum Recolors to Get K Consecutive Black Blocks

Difficulty: Easy
Topics: Strings, Sliding Window

Hint: Use a sliding window to count the number of white blocks in every subarray of length k and find the minimum number to recolor.

Problem Description

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.

Examples

Test Case 1: Single Block (Needs Recoloring)

Input: blocks = "W", k = 1
Output: 1
Explanation:
Only one block is available and it's white. It must be recolored to satisfy the requirement of 1 consecutive black block.

Test Case 2: Single Block (Already Black)

Input: blocks = "B", k = 1
Output: 0
Explanation:
The block is already black, so no recoloring is needed.

Test Case 3: All Blocks White

Input: blocks = "WWWW", k = 2
Output: 2
Explanation:
For any window of 2 blocks in a string of all white blocks, 0 black blocks exist. The optimal strategy is to recolor any two adjacent white blocks to get 2 consecutive black blocks.

Test Case 4: Alternating Colors

Input: blocks = "BWBWBW", k = 3
Output: 1
Explanation:
Consider the window starting at index 0: "BWB" contains 2 black blocks. Recoloring the white block in this window yields 3 consecutive black blocks.

Constraints

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

Category:
Leetcode Problem of the Day
Arrays

Programming Language:
Java

Reference Link:

https://leetcode.com/problems/minimum-recolors-to-get-k-consecutive-black-blocks/description/

Online IDE

Scroll down for output

Java

Output:

Loading component...

Tracking code (View only. In case you want to track the code, click this button):

Main Function:

Main Function is not defined.

Helper Function:

INPUT : blocks = "WBBWWBBWBW"

Output: 3

public static int minimumRecolors(String blocks, int k) {

int bCount = 0;

int ans = Integer.MAX_VALUE;

for (int i = 0; i < blocks.length(); i++) {

if (i - k >= 0 && blocks.charAt(i - k) == 'B'){

bCount--;

}//If End

if (blocks.charAt(i) == 'B') {

bCount++;

}//If End

ans = Math.min(ans, k - bCount);

}//Loop End

return ans;

}//function end

Utility Functions and Global variables:

Utility Function is not required.