CF900E Maximum Questions

Vasya 写下了两个由小写英文字母 'a' 和 'b' 组成的字符串 $s$（长度为 $n$）和 $t$（长度为 $m$）。此外，他还知道字符串 $t$ 的形式为“abab...”，即奇数位置上是字母 'a'，偶数位置上是字母 'b'。 某天早上，Vasya 发现他的字符串被人破坏了。字符串 $s$ 的某些字母被替换成了字符 '?'。 我们称一段从位置 $i$ 到 $i+m-1$ 的连续位置为字符串 $t$ 在 $s$ 中的一次出现，当且仅当 $1 \leq i \leq n-m+1$ 且 $t_1 = s_i, t_2 = s_{i+1}, \ldots, t_m = s_{i+m-1}$。 Vasya 定义字符串 $s$ 的美丽值为字符串 $t$ 在 $s$ 中不重叠出现的最大次数。Vasya 可以将任意位置的 '?' 替换为 'a' 或 'b'（不同位置可以替换成不同的字母）。他希望通过适当的替换，使字符串 $s$ 的美丽值最大。在所有达到最大美丽值的方案中，他希望选一个需要替换最少字符的方案。请你计算，Vasya 需要进行的最少替换次数。

第一行包含一个整数 $n$（$1 \leq n \leq 10^{5}$）——字符串 $s$ 的长度。 第二行包含长度为 $n$ 的字符串 $s$，只包含小写英文字母 'a'、'b' 和字符 '?'。 第三行包含一个整数 $m$（$1 \leq m \leq 10^{5}$）——字符串 $t$ 的长度。字符串 $t$ 规定为奇数位置是 'a'，偶数位置是 'b'。

输出一个整数——为达到 $s$ 的最大美丽值所需要的最小替换次数。

在第一个样例中，字符串 $t$ 为 'a'。唯一的最优方案是把所有的 '?' 都替换为 'a'。 在第二个样例中，通过两次替换，可以将字符串变为 "aba?aba??"。无法获得超过两次出现。 由 ChatGPT 5 翻译