CF2225B Alternating String

我们称一个字符串 $t$ 是交替字符串，如果对于每一个 $i$（$1 \leq i \leq n-1$），都有 $t_i \neq t_{i+1}$ 成立。 给定一个只包含字母 "a" 和／或 "b" 的字符串 $s$。你最多可以对其执行一次如下操作： - 选择一个子串 $s_{l}s_{l+1}\ldots s_{r}$，子串长度至少为 $1$； - 选中该子串后，你可以选择将子串中的所有字母反转，即将每个 "a" 变成 "b"，每个 "b" 变成 "a"（你可以选择执行这一步，也可以选择不执行）； - 反转所选择的子串，即将原字符串 $s_{1}s_{2}\dots s_{l-1}s_{l}s_{l+1}\ldots s_{r}s_{r+1}\ldots s_{n}$ 变成 $s_{1}s_{2}\dots s_{l-1}s_{r}s_{r-1}\ldots s_{l}s_{r+1}\ldots s_{n}$。 注意，执行该操作时，你可以不进行第二步的反转，但第三步的翻转必须执行。例如，对于字符串 $s=$"ababbab"，你可以选择子串 $s_{5}s_{6}s_{7}$ 并执行第二步，得到 "abababa"；也可以选择子串 $s_{1}s_{2}s_{3}s_{4}$ 并不执行第二步，得到 "bababab"。但是第三步总是必做的。 你的任务是判断能否通过一次上述操作（包括可以不操作）把 $s$ 变成任意一个交替字符串。

输入包含多组测试数据。第一行输入测试用例数 $t$（$1 \leq t \leq 10^4$）。接下来每组测试数据一行，一个字符串 $s$（$2 \leq |s| \leq 2 \cdot 10^5$），字符串只包含小写字母 "a" 和／或 "b"。 输入还满足下列条件： - 所有测试用例的字符串长度之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出如下之一： - 如果能将 $s$ 变成交替字符串，则输出 YES； - 否则输出 NO。 可以用任意大小写输出。

在第一个样例中，你可以选择子串 $s_3 s_4 s_5 s_6$ 并跳过第二步，得到字符串 "ababab"。 在第三个样例中，你可以选择子串 $s_1 s_2 s_3 s_4 s_5$ 并执行第二步，得到字符串 "abababa"。 在第四个样例中，原字符串已经是交替字符串。 在第六个样例中，你可以选择子串 $s_2$ 并执行第二步，得到 "bab"。 由 ChatGPT 5 翻译