Question

2379. 得到 K 个黑块的最少涂色次数

English Version

题目描述

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。

给你一个整数 k ，表示想要 连续 黑色块的数目。

每一次操作中，你可以选择一个白色块将它 涂成 黑色块。

请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

 

示例 1：

输入：blocks = "WBBWWBBWBW", k = 7
输出：3
解释：
一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。
得到 blocks = "BBBBBBBWBW" 。
可以证明无法用少于 3 次操作得到 7 个连续的黑块。
所以我们返回 3 。

示例 2：

输入：blocks = "WBWBBBW", k = 2
输出：0
解释：
不需要任何操作，因为已经有 2 个连续的黑块。
所以我们返回 0 。

 

提示：

• n == blocks.length
• 1 <= n <= 100
• blocks[i] 要么是 'W' ，要么是 'B' 。
• 1 <= k <= n

解法

方法一：滑动窗口

我们观察发现，题目实际上求的是一个 $k$ 大小的滑动窗口中白色块的最小数量。

因此，我们只需要遍历字符串 $blocks$，用一个变量 $cnt$ 统计当前窗口中白色块的数量，然后用一个变量 $ans$ 维护最小值即可。

遍历结束后即可得到答案。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为字符串 $blocks$ 的长度。

class Solution:
  def minimumRecolors(self, blocks: str, k: int) -> int:
    ans = cnt = blocks[:k].count('W')
    for i in range(k, len(blocks)):
      cnt += blocks[i] == 'W'
      cnt -= blocks[i - k] == 'W'
      ans = min(ans, cnt)
    return ans

class Solution {
  public int minimumRecolors(String blocks, int k) {
    int cnt = 0;
    for (int i = 0; i < k; ++i) {
      cnt += blocks.charAt(i) == 'W' ? 1 : 0;
    }
    int ans = cnt;
    for (int i = k; i < blocks.length(); ++i) {
      cnt += blocks.charAt(i) == 'W' ? 1 : 0;
      cnt -= blocks.charAt(i - k) == 'W' ? 1 : 0;
      ans = Math.min(ans, cnt);
    }
    return ans;
  }
}

class Solution {
public:
  int minimumRecolors(string blocks, int k) {
    int cnt = count(blocks.begin(), blocks.begin() + k, 'W');
    int ans = cnt;
    for (int i = k; i < blocks.size(); ++i) {
      cnt += blocks[i] == 'W';
      cnt -= blocks[i - k] == 'W';
      ans = min(ans, cnt);
    }
    return ans;
  }
};

func minimumRecolors(blocks string, k int) int {
  cnt := strings.Count(blocks[:k], "W")
  ans := cnt
  for i := k; i < len(blocks); i++ {
    if blocks[i] == 'W' {
      cnt++
    }
    if blocks[i-k] == 'W' {
      cnt--
    }
    if ans > cnt {
      ans = cnt
    }
  }
  return ans
}

function minimumRecolors(blocks: string, k: number): number {
  let cnt = 0;
  for (let i = 0; i < k; ++i) {
    cnt += blocks[i] === 'W' ? 1 : 0;
  }
  let ans = cnt;
  for (let i = k; i < blocks.length; ++i) {
    cnt += blocks[i] === 'W' ? 1 : 0;
    cnt -= blocks[i - k] === 'W' ? 1 : 0;
    ans = Math.min(ans, cnt);
  }
  return ans;
}

impl Solution {
  pub fn minimum_recolors(blocks: String, k: i32) -> i32 {
    let k = k as usize;
    let s = blocks.as_bytes();
    let n = s.len();
    let mut count = 0;
    for i in 0..k {
      if s[i] == b'B' {
        count += 1;
      }
    }
    let mut ans = k - count;
    for i in k..n {
      if s[i - k] == b'B' {
        count -= 1;
      }
      if s[i] == b'B' {
        count += 1;
      }
      ans = ans.min(k - count);
    }
    ans as i32
  }
}

class Solution {
  /**
   * @param String $blocks
   * @param Integer $k
   * @return Integer
   */
  function minimumRecolors($blocks, $k) {
    $cnt = 0;
    for ($i = 0; $i < $k; $i++) {
      if ($blocks[$i] === 'W') {
        $cnt++;
      }
    }
    $min = $cnt;
    for ($i = $k; $i < strlen($blocks); $i++) {
      if ($blocks[$i] === 'W') {
        $cnt++;
      }
      if ($blocks[$i - $k] === 'W') {
        $cnt--;
      }
      $min = min($min, $cnt);
    }
    return $min;
  }
}

#define min(a, b) (((a) < (b)) ? (a) : (b))

int minimumRecolors(char* blocks, int k) {
  int n = strlen(blocks);
  int count = 0;
  for (int i = 0; i < k; i++) {
    count += blocks[i] == 'B';
  }
  int ans = k - count;
  for (int i = k; i < n; i++) {
    count -= blocks[i - k] == 'B';
    count += blocks[i] == 'B';
    ans = min(ans, k - count);
  }
  return ans;
}