Skip to main content
All questions
EasyStrings · Sliding Window

Minimum Repaints for K Black Cells

Written by a community member · · 1 attempt · 100% pass

0

You are given a stripe of checkered paper of length n, where each cell is either white ('W') or black ('B'). Your task is to determine the minimum number of cells that must be recolored from white to black so that the stripe contains at least one segment of k consecutive black cells.

If a segment of k black cells already exists, return 0.

Input:

  • s: a string of length n consisting only of 'W' and 'B'
  • k: an integer with 1 <= k <= len(s)

Output:

  • The minimum number of white cells that must be changed to black so that some substring of length k is all 'B'.

Examples:

  1. Input: s = "BBWBW", k = 3
    Output: 1
    Explanation: Recolor the 'W' at index 2 (0-based) to make the substring "BBB".

  2. Input: s = "BBBB", k = 2
    Output: 0
    Explanation: A segment of 2 consecutive black cells already exists.

Constraints:

  • 1 <= k <= n <= 2 * 10^5
  • The sum of n across all test cases will not exceed 2 * 10^5

Notes:

  • You only need to return the minimum number of recolors for one string.
  • Use an efficient approach suitable for large inputs.