如果对于所有可能的三元组 $$$(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$$$ 是完美平衡的。