CF1673B 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 $ 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.