A Perfectly Balanced String?

题意翻译

我们称字符串 $s$ **完美平衡** 当且仅当对于它的所有子串 $t$，不存在两个字符 $u, v$ 其中 $u, v\in s$，使得在 $t$ 中 $u$ 的出现次数与 $t$ 中 $v$ 的出现次数差大于 $1$。 例如，字符串 `aba` 和 `abc` 是完美平衡的，但 `abb` 却不是，因为对于它的字串 `bb` 有 `b` 出现次数为 $2$，而 `a` 出现次数为 $0$，$2 - 0 > 1$。 给出一个字符串，判断它是否完美对称。 **本题有多组数据。** ### 输入格式 第一行，一个整数 $t\ (1 \leq t \leq 10^4)$，表示数据的组数。 接下来 $t$ 行，每行一个字符串 $s\ (1 \leq \lvert s \rvert \leq 2\times 10^5)$。 对于所有测试用例，所有字符串长度之和 $\sum s \leq 2\times 10^5$。 ### 输出格式 共 $t$ 行，每行一个字符串 `YES` 或 `NO`，表示 $s$ 是否完美平衡。注意评测机对大小写不敏感，也就是说，若答案为 `YES`，则 `YES` `yes` `Yes` `yEs` 都会被判定为正确。

题目描述

Let's call a string $ s $ perfectly balanced if for all possible triplets $ (t,u,v) $ such that $ t $ is a non-empty substring of $ s $ and $ u $ and $ v $ are characters present in $ s $ , the difference between the frequencies of $ u $ and $ v $ in $ t $ is not more than $ 1 $ . For example, the strings "aba" and "abc" are perfectly balanced but "abb" is not because for the triplet ("bb",'a','b'), the condition is not satisfied. You are given a string $ s $ consisting of lowercase English letters only. Your task is to determine whether $ s $ is perfectly balanced or not. A string $ b $ is called a substring of another string $ a $ if $ b $ can be obtained by deleting some characters (possibly $ 0 $ ) from the start and some characters (possibly $ 0 $ ) from the end of $ a $ .

输入输出格式

输入格式

The first line of input contains a single integer $ t $ ( $ 1\leq t\leq 2\cdot 10^4 $ ) denoting the number of testcases. Each of the next $ t $ lines contain a single string $ s $ ( $ 1\leq |s|\leq 2\cdot 10^5 $ ), consisting of lowercase English letters. It is guaranteed that the sum of $ |s| $ over all testcases does not exceed $ 2\cdot 10^5 $ .

输出格式

For each test case, print "YES" if $ s $ is a perfectly balanced string, and "NO" otherwise. You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).

输入输出样例

输入样例 #1

5
aba
abb
abc
aaaaa
abcba

输出样例 #1

YES
NO
YES
YES
NO

说明

Let $ f_t(c) $ represent the frequency of character $ c $ in string $ t $ . For the first testcase we have $ t $ $ f_t(a) $ $ f_t(b) $ $ a $ $ 1 $ $ 0 $ $ ab $ $ 1 $ $ 1 $ $ aba $ $ 2 $ $ 1 $ $ b $ $ 0 $ $ 1 $ $ ba $ $ 1 $ $ 1 $ It can be seen that for any substring $ t $ of $ s $ , the difference between $ f_t(a) $ and $ f_t(b) $ is not more than $ 1 $ . Hence the string $ s $ is perfectly balanced.For the second testcase we have $ t $ $ f_t(a) $ $ f_t(b) $ $ a $ $ 1 $ $ 0 $ $ ab $ $ 1 $ $ 1 $ $ abb $ $ 1 $ $ 2 $ $ b $ $ 0 $ $ 1 $ $ bb $ $ 0 $ $ 2 $ It can be seen that for the substring $ t=bb $ , the difference between $ f_t(a) $ and $ f_t(b) $ is $ 2 $ which is greater than $ 1 $ . Hence the string $ s $ is not perfectly balanced.For the third testcase we have $ 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 $ It can be seen that for any substring $ t $ of $ s $ and any two characters $ u,v\in\{a,b,c\} $ , the difference between $ f_t(u) $ and $ f_t(v) $ is not more than $ 1 $ . Hence the string $ s $ is perfectly balanced.