codeforces-scrape

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

2008E.md (2028B)


      1 Source: https://codeforces.com/problemset/problem/2008/E
      2 
      3 E. Alternating String
      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 Sakurako really loves alternating strings. She calls a string $s$ of lowercase Latin letters an alternating string if characters in the even positions are the same, if characters in the odd positions are the same, and the length of the string is even.
     22 
     23 For example, the strings 'abab' and 'gg' are alternating, while the strings 'aba' and 'ggwp' are not.
     24 
     25 As a good friend, you decided to gift such a string, but you couldn't find one. Luckily, you can perform two types of operations on the string:
     26 
     27 1. Choose an index $i$ and delete the $i$-th character from the string, which will reduce the length of the string by $1$. This type of operation can be performed no more than $1$ time;
     28 2. Choose an index $i$ and replace $s_i$ with any other letter.
     29 
     30 Since you are in a hurry, you need to determine the minimum number of operations required to make the string an alternating one.
     31 
     32 Input
     33 
     34 The first line contains a single integer $t$ ($1 \le t \le 10^4$)  — the number of test cases.
     35 
     36 The first line of each test case contains a single number $n$ ($1 \le n\le 2\cdot 10^5$)  — the length of the string.
     37 
     38 The second line of each test case contains a string $s$, consisting of lowercase Latin letters.
     39 
     40 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     41 
     42 Output
     43 
     44 For each test case, output a single integer — the minimum number of operations required to turn the string $s$ into an alternating one.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 10
     52 
     53 1
     54 
     55 a
     56 
     57 2
     58 
     59 ca
     60 
     61 3
     62 
     63 aab
     64 
     65 5
     66 
     67 ababa
     68 
     69 6
     70 
     71 acdada
     72 
     73 9
     74 
     75 ejibmyyju
     76 
     77 6
     78 
     79 bbccbc
     80 
     81 6
     82 
     83 abacba
     84 
     85 5
     86 
     87 bcbca
     88 
     89 5
     90 
     91 dcbdb
     92 ```
     93 
     94 Output
     95 
     96 ```
     97 1
     98 0
     99 1
    100 1
    101 2
    102 6
    103 2
    104 3
    105 1
    106 1
    107 ```
    108 
    109 Note
    110 
    111 For the string ababa, you can delete the first character to get baba, which is an alternating string.
    112 
    113 For the string acdada, you can change the first two characters to get dadada, which is an alternating string.