codeforces-scrape

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

2003C.md (1971B)


      1 Source: https://codeforces.com/problemset/problem/2003/C
      2 
      3 C. Turtle and Good Pairs
      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 Turtle gives you a string $s$, consisting of lowercase Latin letters.
     22 
     23 Turtle considers a pair of integers $(i, j)$ ($1 \le i \lt j \le n$) to be a pleasant pair if and only if there exists an integer $k$ such that $i \le k \lt j$ and both of the following two conditions hold:
     24 
     25 * $s_k \ne s_{k + 1}$;
     26 * $s_k \ne s_i$ or $s_{k + 1} \ne s_j$.
     27 
     28 Besides, Turtle considers a pair of integers $(i, j)$ ($1 \le i \lt j \le n$) to be a good pair if and only if $s_i = s_j$ or $(i, j)$ is a pleasant pair.
     29 
     30 Turtle wants to reorder the string $s$ so that the number of good pairs is maximized. Please help him!
     31 
     32 Input
     33 
     34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     35 
     36 The first line of each test case contains a single integer $n$ ($2 \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$ of length $n$, consisting of lowercase Latin letters.
     39 
     40 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     41 
     42 Output
     43 
     44 For each test case, output the string $s$ after reordering so that the number of good pairs is maximized. If there are multiple answers, print any of them.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 5
     52 
     53 3
     54 
     55 abc
     56 
     57 5
     58 
     59 edddf
     60 
     61 6
     62 
     63 turtle
     64 
     65 8
     66 
     67 pppppppp
     68 
     69 10
     70 
     71 codeforces
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 acb
     78 ddedf
     79 urtlet
     80 pppppppp
     81 codeforces
     82 ```
     83 
     84 Note
     85 
     86 In the first test case, $(1, 3)$ is a good pair in the reordered string. It can be seen that we can't reorder the string so that the number of good pairs is greater than $1$. bac and cab can also be the answer.
     87 
     88 In the second test case, $(1, 2)$, $(1, 4)$, $(1, 5)$, $(2, 4)$, $(2, 5)$, $(3, 5)$ are good pairs in the reordered string. efddd can also be the answer.