1917B.md (1771B)
1 Source: https://codeforces.com/problemset/problem/1917/B 2 3 B. Erase First or Second Letter 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 You are given a string $s$ of length $n$. Let's define two operations you can apply on the string: 22 23 * remove the first character of the string; 24 * remove the second character of the string. 25 26 Your task is to find the number of distinct non-empty strings that can be generated by applying the given operations on the initial string any number of times (possibly zero), in any order. 27 28 Input 29 30 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows. 31 32 The first line of each test case contains $n$ ($1 \leq n \leq 10^5$) — the length of the string. 33 34 The second line of each test case contains the string $s$. It is guaranteed that the string only contains lowercase letters of the English alphabet. 35 36 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 37 38 Output 39 40 For each test case, output a single integer: the number of distinct non-empty strings you can get. 41 42 Example 43 44 Input 45 46 ``` 47 5 48 49 5 50 51 aaaaa 52 53 1 54 55 z 56 57 5 58 59 ababa 60 61 14 62 63 bcdaaaabcdaaaa 64 65 20 66 67 abcdefghijklmnopqrst 68 ``` 69 70 Output 71 72 ``` 73 5 74 1 75 9 76 50 77 210 78 ``` 79 80 Note 81 82 In the first test case, we can get the following strings: $a$, $aa$, $aaa$, $aaaa$, $aaaaa$. 83 84 In the third test case, for example, the word $ba$ can be reached in the following way: 85 86 * remove the first character of the current string $ababa$, getting $baba$; 87 * remove the second character of the current string $baba$, getting $bba$; 88 * remove the second character of the current string $bba$, getting $ba$.