Mirror in the String (Codeforces 1616B)
Tags: Greedy, strings

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?A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:   $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;  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$$$. 

Input: The first line of input contains one integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$): the number of test cases.The next $$$t$$$ lines contain the description of the test cases, two lines per a test case.In the first line you are given one integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$): the length of the string.The second line contains the string $$$s$$$ consisting of $$$n$$$ lowercase English characters.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case print the lexicographically smallest string you can see.

Note: In the first test case choose $$$k = 1$$$ to obtain "cc".In the second test case choose $$$k = 3$$$ to obtain "cbaabc".In the third test case choose $$$k = 1$$$ to obtain "aa".In the fourth test case choose $$$k = 1$$$ to obtain "bb".

Sample Inputs:
4
10
codeforces
9
cbacbacba
3
aaa
4
bbaa

Sample Outputs:
cc
cbaabc
aa
bb

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def mirror_in_the_string(n, s):
    step_down = False
    last = s[0]
    i = 0
    for i in range(1, n):
        if s[i] > last:
            i -= 1
            break
        if s[i] < last:
            last = s[i]
            step_down = True
        elif step_down:
            continue
        else:
            i -= 1
            break
    return s[:i + 1] + s[:i + 1][::-1]
for _ in range(int(input())):
    n = int(input())
    s = input().decode('ASCII')
    sys.stdout.write(f'{mirror_in_the_string(n, s)}\n')

Solution (Python):
for s in [*open(0)][2::2]:
    a = (*map(ord, s[:-1]), 123)
    i = 1
    while (i > 1) + a[i - 1] > a[i]:
        i += 1
    s = s[:i]
    print(s + s[::-1])

Solution (Python):
for s in [*open(0)][2::2]:
    a = (*map(ord, s[:-1]), 123)
    i = 1
    while (i > 1) + a[i - 1] > a[i]:
        i += 1
    s = s[:i]
    print(s + s[::-1])