codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.