← 返回题目列表

Codeforces · 2202/B

B. ABAB 建设

中文机器翻译题面 查看原题

有一个长度为 $$$n$$$ 的字符串 $$$T$$$,使得 $$$T_i=$$$ 'a' 对于所有奇数 $$$i$$$ 和 $$$T_i=$$$ 'b' 对于所有 $$$i$$$。

有一天,Bob 使用以下算法生成了一个字符串 $$$S$$$。

  1. 将 $$$S$$$ 初始化为空字符串。
  2. 删除 第一 信函或 最后 来自 $$$T$$$ 的信,以及 追加 到$$$S$$$。
  3. 如果 $$$T$$$ 为空,则终止并返回字符串 $$$S$$$。否则,返回第二步。

然后,Bob 将生成的字符串 $$$S$$$ 写在便条上,并在几年后忘记了它。当鲍勃发现这张纸条时,它已经磨损了,有人可能偷偷地更改了一些字母。当然,鲍勃想知道是否有人更改了字符串!

给定一个长度为 $$$n$$$ 的字符串 $$$X$$$,其中包含 'a', 'b', 和 '?'.

请判断是否存在满足以下条件的字符串$$$A$$$:

  • $$$|A|=n$$$;
  • $$$A_i$$$ 是 'a' 或 'b' 对于所有 $$$1 \le i \le n$$$;
  • $$$A_i=X_i$$$ 对于所有 $$$1 \le i \le n$$$ 使得 $$$X_i$$$ 不是 '?';
  • 字符串 $$$A$$$ 可以通过上述算法生成。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$)。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$X$$$,由 'a', 'b', 和 '?'.

保证所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。

输出

如果存在满足所有条件的字符串$$$A$$$,则输出“是" 在单独的一行上。

如果有 没有 满足所有条件的字符串$$$A$$$,输出“NO" 在单独的一行上。

任何情况下都可以输出答案。例如,字符串“是", "是的", "是”也将被视为积极响应。

示例

输入
复制

4
5
ababa
5
baaba
5
?b?ab
6
aa?b?b

输出
复制

YES
NO
YES
NO

注意

对于第二个测试用例,字符串“粑粑" 不能 由上述算法生成。

对于第三个测试用例,字符串“abaab”可以通过上述算法生成:

  1. 最初,$$$T$$$ 是“贝巴" 且 $$$S$$$ 为空。
  2. 删除 $$$T$$$ 中的第一个字母。 $$$T$$$ 变为“粑粑" 和 $$$S$$$ 变为 "a".
  3. 删除 $$$T$$$ 中的第一个字母。 $$$T$$$ 变为“阿巴" 和 $$$S$$$ 变为 "ab".
  4. 删除 $$$T$$$ 中的最后一个字母。 $$$T$$$ 变为“ab" 和 $$$S$$$ 变为 "阿巴".
  5. 删除 $$$T$$$ 中的第一个字母。 $$$T$$$ 变为“b" 和 $$$S$$$ 变为 "abaa".
  6. 删除 $$$T$$$ 中的最后一个字母。 $$$T$$$ 变为空,$$$S$$$ 变为 "abaab".