Lexicographically Smallest Palindrome

Problem Description

Given a string s consisting of lowercase English letters, perform operations (each operation is replacing one character) such that s becomes a palindrome. The goal is to achieve the palindrome with the minimum number of operations. When there are multiple palindromes achievable with the minimum operations, return the lexicographically smallest one.

Key Insights

• Use two pointers (one starting from the beginning and one from the end) to compare characters at symmetric positions.
• If the characters are not equal, change one of them to make them the same. Since we want the lexicographically smallest palindrome, replace the mismatched pair with the smaller character.
• Each mismatched pair requires exactly one replacement.
• For odd length strings, the middle character remains unchanged.
• The operation count is minimized by only changing one side of each mismatched pair rather than both.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, since we traverse from both ends only once. Space Complexity: O(n), for storing the string as an array for in-place modifications.

Solution

The solution uses a greedy two-pointer approach:

1. Convert the string into an array to allow modification.
2. Initialize two pointers: one at the start (i) and one at the end (j).
3. While i is less than j, if the characters at these positions differ, choose the smaller (lexicographically) character and assign it to both positions.
4. Increment i and decrement j.
5. After processing all pairs, join the modified array back into a string and return it. The key trick is choosing the lexicographically smaller character when replacing, ensuring the smallest palindrome is achieved with the minimal number of operations.

Code Solutions