codeforces-scrape

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

2149D.md (2484B)


      1 Source: https://codeforces.com/problemset/problem/2149/D
      2 
      3 D. A and B
      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 Given a string $s$ of length $n$, consisting only of the characters 'a' and 'b'.
     22 
     23 In one operation, you can choose a position $i$ ($1 \le i \le n-1$) and swap the neighboring characters $s_i$ and $s_{i+1}$.
     24 
     25 You need to perform the minimum number of operations to ensure that all characters of one type (either $a$ or $b$) are located strictly together, forming exactly one continuous block.
     26 
     27 Characters of the other type can be positioned either before or after this block, forming two (possibly empty) blocks.
     28 
     29 Examples of valid final forms:
     30 
     31 * 'aaabbbaaa' — all 'b's are located together (one block), 'a's can be both before and after this block;
     32 * 'bbbaaaaaabbb' — all 'a's together, 'b's are at the edges of the string;
     33 * 'aaaaabbbb' or 'bbbbaaaaa' — both types of characters form one continuous block each.
     34 
     35 You need to find the minimum number of described operations required to achieve the specified state.
     36 
     37 Input
     38 
     39 Each test consists of several test cases.
     40 
     41 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.
     42 
     43 The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.
     44 
     45 The second line contains the string $s$ of length $n$, consisting only of the characters 'a' and 'b'.
     46 
     47 It is guaranteed that the sum of the values of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     48 
     49 Output
     50 
     51 For each test case, output one integer — the minimum number of operations required for all characters of one of the two types to form a single continuous block.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 5
     59 
     60 4
     61 
     62 abab
     63 
     64 6
     65 
     66 bababa
     67 
     68 7
     69 
     70 abababa
     71 
     72 2
     73 
     74 ab
     75 
     76 1
     77 
     78 b
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 1
     85 
     86 2
     87 
     88 2
     89 
     90 0
     91 
     92 0
     93 ```
     94 
     95 Note
     96 
     97 In the first test case, the initial string is 'abab':
     98 
     99 * by swapping the neighboring characters at positions $2$ and $3$, we get the string 'aabb';
    100 * or by swapping the characters at positions $1$ and $2$, we get the string 'baab'.
    101 
    102 In both cases, exactly one operation is performed, after which all letters of one type form a single block, so the minimum number of operations is $1$.
    103 
    104 In the fifth input test case, the string consists of a single character 'b'. The single character already forms a continuous block, no swaps are needed, so the minimum number of operations is $0$.