Given a palindrome-like string, replace characters so the final string is a palindrome and is lexicographically smallest among all valid results.
Lexicographically Smallest Palindrome
You are given a string s consisting of lowercase English letters. Your task is to transform it into a palindrome by changing characters as needed.
Among all palindromes that can be obtained using the minimum necessary character changes, return the lexicographically smallest one.
A palindrome reads the same from left to right and right to left.
Idea
For each mirrored pair of characters, choose the smaller character so that the resulting string stays a palindrome and is as small as possible lexicographically.
Input Format
- A single string
sof lowercase English letters. - The string length is at least 1.
Output Format
- Return the lexicographically smallest palindrome obtainable from
sunder the problem rules.
Constraints
1 <= |s| <= $10^{5}$scontains only lowercase English letters.
Example 1
Input
"egcfe"
Output
"efcfe"
Explanation
The mirrored pairs are adjusted to make the string a palindrome. Choosing the smaller character in each pair gives efcfe, which is lexicographically smallest.
Example 2
Input
"abcd"
Output
"abba"
Explanation
Make the first and last characters equal using the smaller one, and do the same for the middle pair. The smallest palindrome is abba.
Show 1 more example
Example 3
Input
"seven"
Output
"neven"
Explanation
After mirroring characters, the lexicographically smallest valid palindrome is neven. This keeps the string palindromic while minimizing the leftmost differing character.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.