codeforces-scrape

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

1748B.md (2782B)


      1 Source: https://codeforces.com/problemset/problem/1748/B
      2 
      3 B. Diverse Substrings
      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 A non-empty digit string is diverse if the number of occurrences of each character in it doesn't exceed the number of distinct characters in it.
     22 
     23 For example:
     24 
     25 * string "7" is diverse because 7 appears in it $1$ time and the number of distinct characters in it is $1$;
     26 * string "77" is not diverse because 7 appears in it $2$ times and the number of distinct characters in it is $1$;
     27 * string "1010" is diverse because both 0 and 1 appear in it $2$ times and the number of distinct characters in it is $2$;
     28 * string "6668" is not diverse because 6 appears in it $3$ times and the number of distinct characters in it is $2$.
     29 
     30 You are given a string $s$ of length $n$, consisting of only digits $0$ to $9$. Find how many of its $\frac{n(n+1)}{2}$ substrings are diverse.
     31 
     32 A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
     33 
     34 Note that if the same diverse string appears in $s$ multiple times, each occurrence should be counted independently. For example, there are two diverse substrings in "77" both equal to "7", so the answer for the string "77" is $2$.
     35 
     36 Input
     37 
     38 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     39 
     40 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the string $s$.
     41 
     42 The second line of each test case contains a string $s$ of length $n$. It is guaranteed that all characters of $s$ are digits from $0$ to $9$.
     43 
     44 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     45 
     46 Output
     47 
     48 For each test case print one integer — the number of diverse substrings of the given string $s$.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 7
     56 
     57 1
     58 
     59 7
     60 
     61 2
     62 
     63 77
     64 
     65 4
     66 
     67 1010
     68 
     69 5
     70 
     71 01100
     72 
     73 6
     74 
     75 399996
     76 
     77 5
     78 
     79 23456
     80 
     81 18
     82 
     83 789987887987998798
     84 ```
     85 
     86 Output
     87 
     88 ```
     89 1
     90 2
     91 10
     92 12
     93 10
     94 15
     95 106
     96 ```
     97 
     98 Note
     99 
    100 In the first test case, the diverse substring is "7".
    101 
    102 In the second test case, the only diverse substring is "7", which appears twice, so the answer is $2$.
    103 
    104 In the third test case, the diverse substrings are "0" ($2$ times), "01", "010", "1" ($2$ times), "10" ($2$ times), "101" and "1010".
    105 
    106 In the fourth test case, the diverse substrings are "0" ($3$ times), "01", "011", "0110", "1" ($2$ times), "10", "100", "110" and "1100".
    107 
    108 In the fifth test case, the diverse substrings are "3", "39", "399", "6", "9" ($4$ times), "96" and "996".
    109 
    110 In the sixth test case, all $15$ non-empty substrings of "23456" are diverse.