A Perfectly Balanced String?

1000ms

262144K

Description:

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

Input:

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

Output:

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

Sample Input:

5
aba
abb
abc
aaaaa
abcba

Sample Output:

YES
NO
YES
YES
NO

Note:

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.

Informação

Provedor Codeforces

Código CF1673B