喵哈喽~, 主人！今天由我，你们最贴心的小猫娘，来带大家解决一道关于黑白条纹的可爱问题！这道题就像在一条长长的猫尾巴上涂色一样有趣，让我们一起来看看吧，喵~ 🐾

Codeforces 1690D - Black and White Stripe

---

题目大意

想象一下，我们有一条长长的纸带，上面有 n 个格子，每个格子要么是黑色的 ('B')，要么是白色的 ('W')。

我们的任务是，要在这条纸带上创造出一段连续的、长度为 k 的全黑格子。为了达到这个目的，我们可以把一些白色的格子涂成黑色。

那么问题来了：最少需要涂黑多少个白色格子，才能实现这个目标呢？

如果纸带上已经存在了长度为 k 的连续黑格子，那我们就不需要动手啦，答案就是 0。

举个例子喵： 假如纸带是 BBWBW，n=5, k=3。

• 我们可以看 s[0..2] 这段 "BBW"，里面有 1 个 'W'。把它涂黑，就变成了 "BBB"，花费是 1。
• 我们也可以看 s[2..4] 这段 "WBW"，里面有 2 个 'W'。把它们都涂黑，就变成了 "BBB"，花费是 2。 所以最少只需要涂 1 个格子，就能得到长度为 3 的连续黑段啦。

---

解题思路

主人，这个问题其实是在问我们：在所有长度为 k 的连续子串中，哪一个子串包含的白色格子 ('W') 最少？因为把一个长度为 k 的子串全部变成黑色，需要涂黑的格子数，就等于这个子串里白色格子的数量嘛。

所以，我们的目标就是找到一个长度为 k 的窗口，使得这个窗口内的 'W' 数量最少。

一个最直接的想法是，遍历所有可能的起始位置，然后对每一个长度为 k 的窗口，都去数一遍里面有多少个 'W'。 比如，我们先数 s[0...k-1] 的 'W' 数量，再数 s[1...k] 的 'W' 数量……一直到 s[n-k...n-1]。 这样做虽然可以，但是当 n 和 k 很大的时候，每次都重新数一遍，效率太低啦，可能会超时哦！(｡>﹏<｡)

这时候，就需要我们聪明的 “滑动窗口” (Sliding Window) 技巧出场啦！喵~

滑动窗口是这样工作的：

1. 初始化：我们先看第一个窗口，也就是从索引 0 到 k-1 的这一段。我们计算出这个窗口里有多少个 'W'，并把它作为我们当前的最小值 min_whites。
2. 滑动：接下来，我们把窗口向右移动一格。这时候，窗口的右边会进来一个新格子，左边会出去一个旧格子。
3. 高效更新：我们不需要重新计算整个新窗口的 'W' 数量！我们只需要根据新进来的格子和旧出去的格子的颜色，来更新上一个窗口的 'W' 数量就行了。
   • 如果新进来的格子是 'W'，那 'W' 的总数就加 1。
   • 如果旧出去的格子是 'W'，那 'W' 的总数就减 1。 这样，我们每次移动窗口，都只需要 O(1) 的时间来更新计数，非常高效！
4. 记录最小值：每次滑动更新后，我们都将当前窗口的 'W' 数量和我们记录的全局最小值 min_whites 比较，如果当前更小，就更新 min_whites。

把整个纸带都滑一遍之后，min_whites 里存的就是我们想要的答案啦！

---

题解代码

这是用 C++ 实现的思路，主人请看~

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

// 这个函数解决一个测试用例喵~
void solve() {
    int n, k;
    std::cin >> n >> k;
    std::string s;
    std::cin >> s;

    int current_whites = 0;
    // 步骤1：初始化第一个窗口
    // 我们先计算出第一个长度为 k 的窗口（从索引 0 到 k-1）里有多少个白色格子 'W'。
    for (int i = 0; i < k; ++i) {
        if (s[i] == 'W') {
            current_whites++;
        }
    }

    // `min_whites` 用来记录所有窗口中，白色格子数量的最小值。
    // 我们先假设第一个窗口就是最小的。
    int min_whites = current_whites;

    // 步骤2 & 3 & 4：滑动窗口并更新最小值
    // 窗口从左向右滑动。循环变量 i 代表新进入窗口的右边界。
    for (int i = k; i < n; ++i) {
        // 更新当前窗口的白色格子数量
        // 新的格子 s[i] 进入窗口
        if (s[i] == 'W') {
            current_whites++;
        }
        // 旧的格子 s[i-k] 离开窗口
        if (s[i - k] == 'W') {
            current_whites--;
        }
        
        // 看看当前窗口的 'W' 数量是不是比我们记录的最小值还要小
        min_whites = std::min(min_whites, current_whites);
    }

    // 最后，把找到的最小需要涂色的格子数打印出来~
    std::cout << min_whites << "\n";
}

int main() {
    // 优化一下输入输出速度，让程序跑得更快一点喵
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

---

知识点小课堂

滑动窗口 (Sliding Window)

滑动窗口是一种非常重要的算法思想，专门用来处理数组或字符串中的连续子区间问题，特别是当这个子区间的长度是固定或者可变的时候。

它的核心就像它的名字一样，想象有一个固定大小的“窗户”，在数据序列上从头到尾“滑动”。每次滑动，我们不是重新分析整个窗户内的所有数据，而是通过移入一个新元素、移出一个旧元素的方式，来高效地更新我们需要的信息（比如和、最大值、或者像这道题里的特定字符数）。

优点：

• 高效：它能把一些问题的时间复杂度从 O(N*K) 优化到 O(N)，其中 N 是总长度，K 是窗口大小。
• 直观：思想比较容易理解，就像在现实世界里移动一个窗户一样。

适用场景：

• 求固定长度 k 的子数组/子串的最大/最小和。
• 求包含特定条件（如最多有 k 个不同字符）的最长子串。
• 以及我们今天这道题，求固定长度 k 的子串中，需要修改次数最少的问题。

前缀和 (Prefix Sum)

除了滑动窗口，这个问题也可以用“前缀和”的思想来解决哦，喵~ 这也是一个非常强大的工具！

思路是：

1. 创建一个辅助数组（比如叫 prefix_W），prefix_W[i] 记录原字符串从开头到第 i-1 个位置总共有多少个 'W'。prefix_W[0] 当然是 0。
2. 计算这个前缀和数组需要 O(N) 的时间。
3. 有了前缀和数组，我们就可以在 O(1) 的时间内查询任意一个子串 s[i...j] 中 'W' 的数量了，公式是 prefix_W[j+1] - prefix_W[i]。
4. 对于这道题，我们想知道 s[i...i+k-1] 中 'W' 的数量，就是 prefix_W[i+k] - prefix_W[i]。
5. 我们只需要遍历所有可能的起始位置 i (从 0 到 n-k)，计算这个差值，然后找到其中的最小值就可以了。

两种方法的时间复杂度都是 O(N)，都非常棒！不过滑动窗口在空间上更优一些，因为它不需要额外开一个数组。

好啦，今天的讲解就到这里啦！希望主人对滑动窗口有了更深的理解，喵~ 如果还有不懂的，随时可以再来问我哦！(＾• ω •＾)