1673B.md (2900B)
1 Source: https://codeforces.com/problemset/problem/1673/B 2 3 B. A Perfectly Balanced String? 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 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. 24 25 You are given a string $s$ consisting of lowercase English letters only. Your task is to determine whether $s$ is perfectly balanced or not. 26 27 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$. 28 29 Input 30 31 The first line of input contains a single integer $t$ ($1\leq t\leq 2\cdot 10^4$) denoting the number of testcases. 32 33 Each of the next $t$ lines contain a single string $s$ ($1\leq |s|\leq 2\cdot 10^5$), consisting of lowercase English letters. 34 35 It is guaranteed that the sum of $|s|$ over all testcases does not exceed $2\cdot 10^5$. 36 37 Output 38 39 For each test case, print "YES" if $s$ is a perfectly balanced string, and "NO" otherwise. 40 41 You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer). 42 43 Example 44 45 Input 46 47 ``` 48 5 49 50 aba 51 52 abb 53 54 abc 55 56 aaaaa 57 58 abcba 59 ``` 60 61 Output 62 63 ``` 64 YES 65 NO 66 YES 67 YES 68 NO 69 ``` 70 71 Note 72 73 Let $f_t(c)$ represent the frequency of character $c$ in string $t$. 74 75 For the first testcase we have 76 77 | | | | 78 | --- | --- | --- | 79 | $t$ | $f_t(a)$ | $f_t(b)$ | 80 | $a$ | $1$ | $0$ | 81 | $ab$ | $1$ | $1$ | 82 | $aba$ | $2$ | $1$ | 83 | $b$ | $0$ | $1$ | 84 | $ba$ | $1$ | $1$ | 85 86 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. 87 88 For the second testcase we have 89 90 | | | | 91 | --- | --- | --- | 92 | $t$ | $f_t(a)$ | $f_t(b)$ | 93 | $a$ | $1$ | $0$ | 94 | $ab$ | $1$ | $1$ | 95 | $abb$ | $1$ | $2$ | 96 | $b$ | $0$ | $1$ | 97 | $bb$ | $0$ | $2$ | 98 99 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. 100 101 For the third testcase we have 102 103 | | | | | 104 | --- | --- | --- | --- | 105 | $t$ | $f_t(a)$ | $f_t(b)$ | $f_t(c)$ | 106 | $a$ | $1$ | $0$ | $0$ | 107 | $ab$ | $1$ | $1$ | $0$ | 108 | $abc$ | $1$ | $1$ | $1$ | 109 | $b$ | $0$ | $1$ | $0$ | 110 | $bc$ | $0$ | $1$ | $1$ | 111 | $c$ | $0$ | $0$ | $1$ | 112 113 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.