[Solution] A Perfectly Balanced String? solution codeforces

A Perfectly Balanced String? solution codeforces – 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 11.

[Solution] A Perfectly Balanced String? solution codeforces

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 00) from the start and some characters (possibly 00) from the end of 𝑎a.

Input

The first line of input contains a single integer 𝑡t (1𝑡21041≤t≤2⋅104) denoting the number of testcases.

Each of the next 𝑡t lines contain a single string 𝑠s (1|𝑠|21051≤|s|≤2⋅105), consisting of lowercase English letters.

It is guaranteed that the sum of |𝑠||s| over all testcases does not exceed 21052⋅105.

[Solution] A Perfectly Balanced String? solution codeforces

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

Example
input

Copy
5
aba
abb
abc
aaaaa
abcba
output

Copy
YES
NO
YES
YES
NO

[Solution] A Perfectly Balanced String? solution codeforces

Let 𝑓𝑡(𝑐)ft(c) represent the frequency of character 𝑐c in string 𝑡t.

For the first testcase we have

𝑡t 𝑓𝑡(𝑎)ft(a) 𝑓𝑡(𝑏)ft(b)
𝑎a 11 00
𝑎𝑏ab 11 11
𝑎𝑏𝑎aba 22 11
𝑏b 00 11
𝑏𝑎ba 11 11

It can be seen that for any substring 𝑡t of 𝑠s, the difference between 𝑓𝑡(𝑎)ft(a) and 𝑓𝑡(𝑏)ft(b) is not more than 11. Hence the string 𝑠s is perfectly balanced. 

For the second testcase we have

𝑡t 𝑓𝑡(𝑎)ft(a) 𝑓𝑡(𝑏)ft(b)
𝑎a 11 00
𝑎𝑏ab 11 11
𝑎𝑏𝑏abb 11 22
𝑏b 00 11
𝑏𝑏bb 00 22

It can be seen that for the substring 𝑡=𝑏𝑏t=bb, the difference between 𝑓𝑡(𝑎)ft(a) and 𝑓𝑡(𝑏)ft(b) is 22 which is greater than 11. Hence the string 𝑠s is not perfectly balanced.

A Perfectly Balanced String? solution codeforces

For the third testcase we have

𝑡t 𝑓𝑡(𝑎)ft(a) 𝑓𝑡(𝑏)ft(b) 𝑓𝑡(𝑐)ft(c)
𝑎a 11 00 00
𝑎𝑏ab 11 11 00
𝑎𝑏𝑐abc 11 11 11
𝑏b 00 11 00
𝑏𝑐bc 00 11 11
𝑐c 00 00 11

 

It can be seen that for any substring 𝑡t of 𝑠s and any two characters 𝑢,𝑣{𝑎,𝑏,𝑐}u,v∈{a,b,c}, the difference between 𝑓𝑡(𝑢)ft(u) and 𝑓𝑡(𝑣)ft(v) is not more than 11. Hence the string 𝑠s is perfectly balanced.

 

For Solution

Click here

Leave a Comment