Minimum Recolors to Get K Consecutive Black Blocks

🏠 ⬅️ ➡️

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
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    character(len=100) :: blocks
    integer :: n, k, i, j, count, min_ops

    ! read input
    read(*,*) blocks
    read(*,*) n
    read(*,*) k

    ! initialize variables
    count = 0
    min_ops = 1000000000

    ! loop through blocks
    do i = 1, n
        if (blocks(i:i) == 'W') then
            count = 0
        else
            count = count + 1
        end if

        ! check for k consecutive black blocks
        if (count >= k) then
            min_ops = min(min_ops, i - k + 1)
        end if
    end do

    ! print output
    write (*,*) min_ops

end program main
❌ Compiled
❌ Executed
❌ Correct 
module main

implicit none

integer :: n, k, i, j, count, min_operations
character(len=1) :: blocks(100)

! Read input
read(*,*) n
read(*,*) blocks
read(*,*) k

! Initialize variables
min_operations = 0
count = 0

! Iterate through the blocks
do i = 1, n
    if (blocks(i) == 'B') then
        count = count + 1
    else
        count = 0
    end if
    
    ! Check if we have reached k consecutive black blocks
    if (count == k) then
        min_operations = min_operations + 1
        count = 0
    end if
end do

! Print output
write(*,*) min_operations

end module
🌐 Data from online sources 
def min_operations(blocks, k):
    n = len(blocks)
    res = k
    w = b = 0
    i = j = 0

    while j < n:
        if blocks[j] == 'W':
            w += 1
        while b > k or (b == k and blocks[i] == 'B'):
            if blocks[i] == 'W':
                w -= 1
                i += 1
            else:
                b -= 1
                i += 1
        if b == k:
            res = min(res, w)
        else:
            b += 1
        j += 1

    return res

The algorithm keeps a sliding window over the blocks string. It simultaneously counts the number of black blocks, b, and white blocks, w, in the sliding window.

Initially, both the left and right pointers of the sliding window, i and j, are set to 0. We iterate over the string using the right pointer, j. When the black count b equals k, we minimize the answer by taking the minimum of the current result and the white count w.

If the black count b is greater than k, or equal to k but the left pointer i points to a black block, we need to adjust the left pointer to keep only k black blocks in the sliding window. To do this, we increment the left pointer and decrement the corresponding color count.

Finally, we return the minimum operation count we found.

Notice that the algorithm executes in linear time. This is because each block is visited exactly twice (once by the right pointer and once by the left pointer), and the color counts are updated during the traversal. This leads to an overall time complexity of O(n) for the algorithm.

🌐 Data from online sources 
int minOperations(string blocks, int k) {
    int n = blocks.length(), res = k, w = 0, b = 0;
    for (int i = 0, j = 0; j < n; ++j) {
        if (blocks[j] == 'W') w++;
        while (b > k || (b == k && blocks[i] == 'B')) {
            if (blocks[i++] == 'W') w--;
            else b--;
        }
        if (b == k) res = min(res, w);
        else b++;
    }
    return res;
}

The algorithm keeps a sliding window over the blocks string. It simultaneously counts the number of black blocks, b, and white blocks, w, in the sliding window.

Initially, both the left and right pointers of the sliding window, i and j, are set to 0. We iterate over the string using the right pointer, j. When the black count b equals k, we minimize the answer by taking the minimum of the current result and the white count w.

If the black count b is greater than k, or equal to k but the left pointer i points to a black block, we need to adjust the left pointer to keep only k black blocks in the sliding window. To do this, we increment the left pointer and decrement the corresponding color count.

Finally, we return the minimum operation count we found.

Notice that the algorithm executes in linear time. This is because each block is visited exactly twice (once by the right pointer and once by the left pointer), and the color counts are updated during the traversal. This leads to an overall time complexity of O(n) for the algorithm.