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.