1800D.md (1714B)
1 Source: https://codeforces.com/problemset/problem/1800/D 2 3 D. Remove Two Letters 4 5 time limit per test 6 7 2 seconds 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 Dmitry has a string $s$, consisting of lowercase Latin letters. 22 23 Dmitry decided to remove two consecutive characters from the string $s$ and you are wondering how many different strings can be obtained after such an operation. 24 25 For example, Dmitry has a string "aaabcc". You can get the following different strings: "abcc"(by deleting the first two or second and third characters), "aacc"(by deleting the third and fourth characters),"aaac"(by deleting the fourth and the fifth character) and "aaab" (by deleting the last two). 26 27 Input 28 29 The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — number of test cases. 30 31 The descriptions of the test cases follow. 32 33 The first line of the description of each test case contains an integer $n$ ($3 \le n \le 2 \cdot 10^5$). 34 35 The second line of the description of each test case contains a string $s$ of length $n$ consisting of lowercase Latin letters. 36 37 It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case print one integer — the number of distinct strings that can be obtained by removing two consecutive letters. 42 43 Example 44 45 Input 46 47 ``` 48 7 49 50 6 51 52 aaabcc 53 54 10 55 56 aaaaaaaaaa 57 58 6 59 60 abcdef 61 62 7 63 64 abacaba 65 66 6 67 68 cccfff 69 70 4 71 72 abba 73 74 5 75 76 ababa 77 ``` 78 79 Output 80 81 ``` 82 4 83 1 84 5 85 3 86 3 87 3 88 1 89 ``` 90 91 Note 92 93 The first example is explained in the statement. 94 95 In the third example, the following strings are obtained: "cdef", "adef", "abef", "abcf", "abcd". 96 97 In the seventh example, any deletion will result in the string "aba".