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

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

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.