Minimum Recolors to Get K Consecutive Black Blocks

EasyStringSliding Window

문제 설명

문자 W 또는 B 로 이루어진 문자열 blocks가 주어진다.
정수 k가 주어지며, 연속된 k개의 B 블록이 필요하다.
W블록을 B 블록으로 변경할 수 있다.
k개의 연속된 B 블록을 만들 수 있는 최소한의 변경 횟수를 반환한다.

문제 풀이

`Sliding Window`

문자열을 순회하면서 W의 개수를 계산
윈도우의 크기가 k가 되면 최소 변경 횟수를 갱신
윈도우를 이동할 때, 앞의 문자(start 위치)를 제거

function minimumRecolors(blocks: string, k: number): number {
  const n = blocks.length;
  let minColorChange = n;
 
  let start = 0;
  let whiteCount = 0;
  for (let end = 0; end < n; end++) {
    if (blocks[end] === 'W') {
      whiteCount += 1;
    }
 
    if (end - start + 1 === k) {
      minColorChange = Math.min(minColorChange, whiteCount);
      if (blocks[start] === 'W') {
        whiteCount -= 1;
      }
      start += 1;
    }
  }
  return minColorChange;
}

복잡도

시간 복잡도: $O(n)$
공간 복잡도: $O(1)$

LeetCode

Minimum Recolors to Get K Consecutive Black Blocks

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