CF1673B.A Perfectly Balanced String?

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

我们称一个字符串 $s$ 是完美平衡的，如果对所有可能的三元组 $(t,u,v)$（其中 $t$ 是 $s$ 的一个非空子串，且 $u$ 和 $v$ 均为 $s$ 中出现过的字符），$t$ 中 $u$ 与 $v$ 的出现频数之差的绝对值不超过 $1$。

例如，字符串 "aba" 和 "abc" 是完美平衡的，但 "abb" 不是，因为对三元组 ("bb", 'a', 'b')，该条件不成立。

你将得到一个仅由小写英文字母组成的字符串 $s$。你的任务是判断 $s$ 是否为完美平衡的。

若字符串 $b$ 可通过从字符串 $a$ 的开头删除若干字符（可能为 $0$ 个）且从结尾删除若干字符（可能为 $0$ 个）而得到，则称 $b$ 是 $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$.

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

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

保证所有测试用例中 $|s|$ 的总和不超过 $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).

对于每个测试用例，如果 $s$ 是一个完全平衡的字符串，则输出 "YES"；否则输出 "NO"。

你可以以任意大小写形式输出每个字母（例如，"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.

令 $f_t(c)$ 表示字符 $c$ 在字符串 $t$ 中的出现频数。

对于第一个测试用例，我们有

$t$

$f_t(a)$

$f_t(b)$

$a$

$1$

$0$

$ab$

$1$

$1$

$aba$

$2$

$1$

$b$

$0$

$1$

$ba$

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

$abb$

$1$

$2$

$b$

$0$

$1$

$bb$

$0$

$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$ 是完美平衡的。