CF1852D Miriany and Matchstick

Miriany 的火柴棒是一个 $2 \times n$ 的网格，需要用字符 A 或 B 填充。 他已经填好了第一行，现在希望你来填第二行。你需要填充第二行，使得相邻格子中字符不同的格子的对数等于 $k$。如果无法做到，请输出不可能。 $^\dagger$ 相邻且字符不同的格子对，指的是一对格子 $(r_1, c_1)$ 和 $(r_2, c_2)$（$1 \le r_1, r_2 \le 2$，$1 \le c_1, c_2 \le n$），满足 $|r_1 - r_2| + |c_1 - c_2| = 1$，且 $(r_1, c_1)$ 和 $(r_2, c_2)$ 中的字符不同。

第一行包含一个整数 $t$，表示测试用例的数量（$1 \leq t \leq 1000$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2 \cdot 10^5, 0 \leq k \leq 3 \cdot n$），分别表示火柴棒的列数和要求的相邻且字符不同的格子对数。 接下来一行包含一个长度为 $n$ 的字符串 $s$（$s_i$ 为 A 或 B），表示 Miriany 已经填好的火柴棒第一行。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果不存在一种方案能使相邻且字符不同的格子对数等于 $k$，输出 "NO"。 否则，输出 "YES"，并输出一行长度为 $n$ 的字符串，表示 Miriany 的火柴棒第二行的合法填法。如果有多种答案，输出任意一种均可。

在第一个测试用例中，可以证明不存在一种填法能使第二行填好后 $k = 1$。 对于第二个测试用例，BABB 是一种可行的答案。 如下所示，填入 BABB 后的网格为： $\begin{array}{|c|c|c|c|} \hline A & A & A & A \\ \hline B & A & B & B \\ \hline \end{array}$ 下方用红色标出了字符不同的格子对： $\begin{array}{|c|c|c|c|} \hline \color{red}{A} & A & A & A \\ \hline \color{red}{B} & A & B & B \\ \hline \end{array}$ —————————————————— $\begin{array}{|c|c|c|c|} \hline A & A & \color{red}{A} & A \\ \hline B & A & \color{red}{B} & B \\ \hline \end{array}$ —————————————————— $\begin{array}{|c|c|c|c|} \hline A & A & A & \color{red}{A} \\ \hline B & A & B & \color{red}{B} \\ \hline \end{array}$ —————————————————— $\begin{array}{|c|c|c|c|} \hline A & A & A & A \\ \hline \color{red}{B} & \color{red}{A} & B & B \\ \hline \end{array}$ —————————————————— $\begin{array}{|c|c|c|c|} \hline A & A & A & A \\ \hline B & \color{red}{A} & \color{red}{B} & B \\ \hline \end{array}$ 一共有 $5$ 对，满足 $k$ 的要求。 由 ChatGPT 4.1 翻译