B. A Perfectly Balanced String?time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet'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.InputThe 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.OutputFor 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).ExampleInput
5
aba
abb
abc
aaaaa
abcba
Output
YES
NO
YES
YES
NO
NoteLet f_t(c) represent the frequency of character c in string t.For the first testcase we have tf_t(a)f_t(b)a10ab11aba21b01ba11 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 tf_t(a)f_t(b)a10ab11abb12b01bb02 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 tf_t(a)f_t(b)f_t(c)a100ab110abc111b010bc011c001It 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.
5
aba
abb
abc
aaaaa
abcba

YES NO YES YES NO 
['brute force', 'greedy', 'strings', '*1100']