1616B.md (1703B)
1 Source: https://codeforces.com/problemset/problem/1616/B 2 3 B. Mirror in the String 4 5 time limit per test 6 7 1 second 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 You have a string $s_1 s_2 \ldots s_n$ and you stand on the left of the string looking right. You want to choose an index $k$ ($1 \le k \le n$) and place a mirror after the $k$-th letter, so that what you see is $s_1 s_2 \ldots s_k s_k s_{k - 1} \ldots s_1$. What is the lexicographically smallest string you can see? 22 23 A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds: 24 25 * $a$ is a prefix of $b$, but $a \ne b$; 26 * in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$. 27 28 Input 29 30 The first line of input contains one integer $t$ ($1 \leq t \leq 10\,000$): the number of test cases. 31 32 The next $t$ lines contain the description of the test cases, two lines per a test case. 33 34 In the first line you are given one integer $n$ ($1 \leq n \leq 10^5$): the length of the string. 35 36 The second line contains the string $s$ consisting of $n$ lowercase English characters. 37 38 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 39 40 Output 41 42 For each test case print the lexicographically smallest string you can see. 43 44 Example 45 46 Input 47 48 ``` 49 4 50 10 51 codeforces 52 9 53 cbacbacba 54 3 55 aaa 56 4 57 bbaa 58 ``` 59 60 Output 61 62 ``` 63 cc 64 cbaabc 65 aa 66 bb 67 ``` 68 69 Note 70 71 In the first test case choose $k = 1$ to obtain "cc". 72 73 In the second test case choose $k = 3$ to obtain "cbaabc". 74 75 In the third test case choose $k = 1$ to obtain "aa". 76 77 In the fourth test case choose $k = 1$ to obtain "bb".