← 返回题目列表

Codeforces · 1673/B

B. 一根完美平衡的弦?

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

如果对于所有可能的三元组 $$$(t,u,v)$$$ 使得 $$$t$$$ 是 $$$s$$$ 的非空子串,并且 $$$u$$$ 和 $$$v$$$ 是 $$$s$$$ 中出现的字符,那么我们称字符串 $$$s$$$ 完美平衡,$$$u$$$ 和 $$$u$$$ 的频率之间的差异$$$t$$$ 中的 $$$v$$$ 不超过 $$$1$$$。

例如,字符串“aba”和“abc”是完美平衡的,但“abb”则不是,因为对于三元组(“bb”,'a','b'),不满足条件。

给你一个仅由小写英文字母组成的字符串 $$$s$$$。您的任务是确定 $$$s$$$ 是否完全平衡。

如果 $$$b$$$ 可以通过从 $$$a$$$ 开头删除一些字符(可能是 $$$0$$$)和从 $$$a$$$ 末尾删除一些字符(可能是 $$$0$$$)来获得,则字符串 $$$b$$$ 被称为另一个字符串 $$$a$$$ 的子字符串。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 2\cdot 10^4$$$) 表示测试用例的数量。

接下来的 $$$t$$$ 行包含一个字符串 $$$s$$$ ($$$1\leq |s|\leq 2\cdot 10^5$$$),由小写英文字母组成。

保证所有测试用例的 $$$|s|$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,如果 $$$s$$$ 是完美平衡的字符串,则打印“YES”,否则打印“NO”。

您可以在任何情况下打印每个字母(例如,“YES”、“Yes”、“yes”、“yEs”都将被识别为肯定答案)。

示例

输入 #1

5
aba
abb
abc
aaaaa
abcba

输出 #1

YES
NO
YES
YES
NO

注意

让$$$f_t(c)$$$表示字符$$$c$$$在字符串$$$t$$$中的频率。

对于第一个测试用例,我们有$$$t$$$$$$f_t(a)$$$$$$f_t(b)$$$$$$a$$$$$$1$$$$$$0$$$$$$ab$$$$$$1$$$$$$1$$$$$$ 1$$$$$$aba$$$$$$2$$$$$$1$$$$$$b$$$$$$0$$$$$$1$$$$$$ba$$$$$$1$$$$$1$$$1$$$可以看出,对于$$$s$$$的任意子串$$$t$$$,$$$f_t(a)$$$和$$$f_t(b)$$$之间的差异不大于$$$1$$$。因此字符串 $$$s$$$ 是完美平衡的。

对于第二个测试用例,我们有$$$t$$$$$$f_t(a)$$$$$$f_t(b)$$$$$$a$$$$$$1$$$$$$0$$$$$$ab$$$$$$1$$$$$$1$$$$$$ 1$$$$$$abb$$$$$$1$$$$$$2$$$$$$b$$$$$$0$$$$$$1$$$$$$bb$$$$$$0$$$$$$2$$$2$$$可以看出,对于子串$$$t=bb$$$,$$$f_t(a)$$$与$$$f_t(b)$$$之间的差异为$$$2$$$,大于$$$1$$$。因此字符串 $$$s$$$ 并不完全平衡。

对于第三个测试用例,我们有$$$t$$$$$$f_t(a)$$$$$$f_t(b)$$$$$$f_t(c)$$$$$$a$$$$$$1$$$$$$0$$$$$$0$$$$$$ab$$$$$$1$$$$$$1$$$$$$0$$$$$$abc$ $$$$$1$$$$$$1$$$$$$1$$$$$$b$$$$$$0$$$$$$1$$$$$0$$$$$$bc$$$$$$0$$$$$$1$$$$$$1$$$$$$c$$$$$$0$$$$$$0$$$$$$1$$$

可以看出,对于$$$s$$$的任意子串$$$t$$$和$$$u,v\in\{a,b,c\}$$$中的任意两个字符,$$$f_t(u)$$$和$$$f_t(v)$$$之间的差异不大于$$$1$$$。因此字符串 $$$s$$$ 是完美平衡的。