aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--min_recolour_k_block.c39
-rw-r--r--min_recolour_k_block.py42
2 files changed, 81 insertions, 0 deletions
diff --git a/min_recolour_k_block.c b/min_recolour_k_block.c
new file mode 100644
index 0000000..253fad2
--- /dev/null
+++ b/min_recolour_k_block.c
@@ -0,0 +1,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
+}
diff --git a/min_recolour_k_block.py b/min_recolour_k_block.py
new file mode 100644
index 0000000..c4d8d30
--- /dev/null
+++ b/min_recolour_k_block.py
@@ -0,0 +1,42 @@
+# 2379. 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 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.
+"""
+
+
+class Solution(object):
+ def minimumRecolors(self, blocks, k):
+ """
+ :type blocks: str
+ :type k: int
+ :rtype: int
+ """
+ n, min_op, flips, cnt, i = len(blocks), float("inf"), 0, 0, 0
+ for j in range(n):
+ if blocks[j] == "W":
+ flips += 1
+ cnt += 1
+ elif blocks[j] == "B":
+ cnt += 1
+ if cnt == k:
+ min_op = min(min_op, flips)
+ if blocks[i] == "W":
+ flips -= 1
+ cnt -= 1
+ else:
+ cnt -= 1
+ i += 1
+ return min_op
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minimumRecolors(blocks="WBBWWBBWBW", k=7))
+ print(obj.minimumRecolors(blocks="WBWBBBW", k=2))