aboutsummaryrefslogtreecommitdiff
path: root/min_recolour_k_block.c
blob: 253fad2394d57aa6e5c51585cc36a06490521acf (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 2379. Minimum Recolors to Get K Consecutive Black Blocks
#include "leetcode.h"

/*
 * you are given a 0-indexed string 'blocks' of length 'n' where 'blocks[i]' is
 * either 'W' or 'B', representing the colour of the i'th block. the characters
 * 'W' and 'B' denote the colours 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 recolour a white block such that it becomes
 * a black block. return the minimum number of operations needed such that there
 * is at least one occurence of 'k' consecutive black blocks.
 */

int minimumRecolors(char *blocks, int k) {
  int n = strlen(blocks), min = INT_MAX, flips = 0, cnt = 0, i = 0;
  for (int j = 0; j < n; ++j) {
    if (blocks[j] == 'W') {
      flips++;
      cnt++;
    } else if (blocks[j] == 'B')
      cnt++;
    if (cnt == k) {
      min = fmin(min, flips);
      if (blocks[i] == 'W') {
        flips--;
        cnt--;
      } else
        cnt--;
      i++;
    }
  }
  return min;
}

int main() {
  char *b1 = "WBBWWBBWBW", *b2 = "WBWBBBW";
  printf("%d\n", minimumRecolors(b1, 7)); // expect: 3
  printf("%d\n", minimumRecolors(b2, 2)); // expect: 0
}