Make a Minimum-Change Palindrome with Lexicographic Tie-Breaking
Company: IBM
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
# Make a Minimum-Change Palindrome with Lexicographic Tie-Breaking
You are given a string `s` containing only lowercase English letters. One operation replaces one character with any other lowercase English letter.
Make `s` a palindrome using the fewest possible operations. Among the palindromes obtainable with that minimum number of operations, return the lexicographically smallest one.
A palindrome reads the same from left to right and right to left. For equal-length strings, lexicographic order is determined by the first position where their characters differ: the string with the earlier letter at that position is smaller.
### Examples
**Example 1**
```text
Input: s = "fzbcd"
Output: "dcbcd"
```
Two changes are necessary: the outer letters `f` and `d` differ, and the next pair `z` and `c` differs. Changing `f` to `d` and `z` to `c` gives the smallest palindrome among the two-change possibilities. The middle `b` stays unchanged.
**Example 2**
```text
Input: s = "azba"
Output: "abba"
```
The outer letters already agree. One replacement of `z` with `b` makes the string a palindrome; choosing `b` rather than `z` gives the smaller one-change result.
### Constraints
- `1 <= s.length <= 1000`.
- `s` contains only lowercase English letters.
### Clarifying Questions
- Which objective comes first? Minimize the number of replacements; apply lexicographic order only to results tied on that minimum.
- Can characters be inserted, removed, or rearranged? No; only single-character replacements are allowed.
- Must the minimum operation count be returned? No; return the resulting palindrome string.
- Does the middle character of an odd-length string need a matching partner? No; it matches itself.
### C++ Interface
```cpp
class Solution {
public:
string makeSmallestPalindrome(string s) {
}
};
```
### Reasoning Checkpoints
- Separate the minimum-edit requirement from the tie-breaking requirement.
- Account for characters that already match and for an unpaired middle character.
- Explain why a local choice cannot force extra replacements elsewhere.
```hint Mirrored positions
What must be true of the characters at positions i and s.length - 1 - i in any palindrome?
```
Overview: Replace lowercase letters to form a palindrome with the fewest changes, then choose the lexicographically smallest result among equally short edit sequences.