codeforces-scrape

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

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".