CF2202B ABAB Construction

有一个长度为 $n$ 的字符串 $T$，满足所有奇数位置 $T_i$ 都为 'a'，所有偶数位置 $T_i$ 都为 'b'。 有一天，Bob 用如下算法生成了一个字符串 $S$： 1. 令 $S$ 为空字符串。 2. 从 $T$ 的首字母或尾字母中任选其一，取走并追加到 $S$ 的末尾。 3. 若 $T$ 为空，则结束并返回字符串 $S$。否则，返回步骤 2。 之后，Bob 将生成的字符串 $S$ 写在纸条上，若干年后他发现这张纸条已经磨损，甚至可能有人偷偷改动过其中一些字母。现在，Bob 想知道字符串是否被改动过！ 你得到一个长度为 $n$ 的字符串 $X$，$X$ 只包含 'a'、'b' 和 '?'。 请你判断，是否存在一个字符串 $A$，使得满足以下条件： - $|A|=n$； - 每个 $A_i$ 只能为 'a' 或 'b'； - 对于 $1 \le i \le n$，若 $X_i$ 不是 '?'，则 $A_i = X_i$； - 字符串 $A$ 可以通过上述算法从字符串 $T$ 生成。

每组测试数据包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行为一个整数 $n$（$1 \le n \le 200\,000$）。 每个测试用例的第二行为一个长度为 $n$ 的字符串 $X$，只包含小写字母 'a'、'b' 和 '?'。 保证所有测试用例的 $n$ 之和不超过 $200\,000$。

对于每个测试用例，如果存在满足条件的字符串 $A$，则输出一行 "YES"（不区分大小写）。 否则输出一行 "NO"。

对于第二个测试用例，字符串 "baaba" 无法通过上述算法生成。 对于第三个测试用例，字符串 "abaab" 可以通过上述算法生成： 1. 初始时，$T=$"ababa"，$S$ 为空。 2. 移除 $T$ 的首字母，$T$ 变为 "baba"，$S$ 变为 "a"。 3. 移除 $T$ 的首字母，$T$ 变为 "aba"，$S$ 变为 "ab"。 4. 移除 $T$ 的尾字母，$T$ 变为 "ab"，$S$ 变为 "aba"。 5. 移除 $T$ 的首字母，$T$ 变为 "b"，$S$ 变为 "abaa"。 6. 移除 $T$ 的尾字母，$T$ 变为空，$S$ 变为 "abaab"。 由 ChatGPT 5 翻译