codeforces-scrape

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

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