A Perfectly Balanced String?
Contest: Codeforces Round 785 (Div. 2)
Difficulty rating: 1100
Tags: brute force, greedy, strings

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
5
aba
abb
abc
aaaaa
abcba

Example output:
YES
NO
YES
YES
NO

Editorial:
Let the number of distinct characters in $$$s$$$ be $$$k$$$ and length of $$$s$$$ be $$$n$$$. Then, $$$s$$$ will be perfectly balanced if and only if $$$s_{i}, s_{i+1}, \ldots, s_{i+k}$$$ are all pairwise distinct for every $$$i$$$ in the range $$$1\leq i\leq n-k$$$.
Proof why this condition is necessary:
If there exists some $$$i$$$ in the range $$$1\leq i\leq n-k$$$ for which the characters $$$s_{i}, s_{i+1}, \ldots, s_{i+k}$$$ are not pairwise distinct, there will be atleast one character $$$u$$$ in the substring $$$t=s_{i} s_{i+1}\ldots s_{i+k}$$$ such that $$$f_t(u)\geq 2$$$ and by pigeonhole principle, there will be atleast one character $$$v$$$ present in $$$s$$$ such that $$$f_t(v)=0$$$. So, for the triple $$$(t,u,v)$$$, $$$f_t(u)-f_t(v)\geq 2$$$, violating the criteria for the $$$s$$$ to be perfectly balanced.
Proof why this condition is sufficient:
Suppose the following condition is met. Let's pick up any substring $$$t=s_is_{i+1}\ldots s_j$$$. Let's divide $$$t$$$ into $$$\Big\lceil \frac{j-i+1}{k}\Big\rceil$$$ blocks each of length $$$k$$$ except probably the last block. For each of these blocks, the frequency of all characters is equal to $$$1$$$ (because there are $$$k$$$ distinct characters in a block as well as in $$$s$$$) and for the last block, the frequency of some characters is equal to $$$1$$$ wheras the frequency of rest of the characters is equal to $$$0$$$. So, the frequency of some characters in $$$t$$$ will be equal to $$$\Big\lceil \frac{j-i+1}{k}\Big\rceil$$$ while that for the other characters will be equal to $$$\Big\lceil \frac{j-i+1}{k}\Big\rceil-1$$$. If we pick any two characters $$$u$$$ and $$$v$$$, $$$\lvert f_t(u)-f_t(v)\rvert\leq 1$$$ meaning that $$$s$$$ is perfectly balanced.
Bonus task: Prove that the condition is equivalent to the following two conditions -
1. The first $$$k$$$ characters of $$$s$$$ are pairwise distinct.
2. For each $$$i$$$ in the range $$$1\leq i\leq n-k$$$, $$$s_i=s_{i+k}$$$.