A vintage combination lock opens only when the sequence of lowercase-letter labels engraved around its dial reads identically from either end -- that is, when the label sequence is a palindrome. Corrosion has altered some of the labels, so the current sequence may no longer be symmetric. A locksmith wants to re-engrave as few labels as possible so the sequence becomes a palindrome again. Among every re-engraving that achieves that minimum number of changes, the locksmith always picks the lexicographically smallest resulting sequence (comparing the sequences letter by letter, with 'a' the smallest letter). Given the current label sequence, output that final sequence.
n -- the number of labels on the dial.s of length n consisting of lowercase English letters -- the current label sequence.Print the lexicographically smallest palindrome obtainable from s using the minimum possible number of single-character label changes.
1 <= n <= 1000s consists only of lowercase English letters.Example 1
Input
5 abcda
Expected
abcba
Explanation
Comparing the sequence to its mirror, only the pair at positions 2 and 4 (1-indexed), b and d, disagree; every other pair (a/a at the ends and the middle c) already matches. Re-engraving one of the two mismatched labels to match the other costs exactly one change, and choosing the smaller letter, b, for both positions gives the lexicographically smallest palindrome achievable with that one change: abcba.
Example 2
Input
7 racecar
Expected
racecar
Explanation
The sequence already reads the same forwards and backwards, so zero relabelling is needed and the sequence itself is the answer.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →