Smallest Palindromic Rearrangement
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You are given a lowercase English string `s` that is already a palindrome. Rearrange its characters to form the lexicographically smallest possible palindrome, and return that string.
Use every original character exactly once, preserving all character multiplicities. Lexicographic order compares the first differing character; the string with the smaller character there comes first.
### C++ Interface
```cpp
class Solution {
public:
string smallestPalindrome(string s) {
}
};
```
### Examples
**Example 1**
```text
Input: s = "cbaabc"
Output: "abccba"
```
Each of `a`, `b`, and `c` occurs twice. The returned string is a palindrome with those same counts and is the lexicographically earliest such rearrangement.
**Example 2**
```text
Input: s = "baaab"
Output: "ababa"
```
The distinct palindromic rearrangements are `ababa` and `baaab`. Since `ababa` starts with the smaller letter, it is the required result.
### Constraints
- `1 <= s.length <= 100000`.
- `s` contains only lowercase English letters.
- `s` is guaranteed to be palindromic.
### Clarifying Questions
- Is returning the original string always sufficient? No. It is valid, but another palindrome with the same letters may be lexicographically smaller.
- May any letter be added or discarded? No. Every multiplicity must remain unchanged.
- What if several rearrangements of identical copies produce the same string? They do not create a different result; return the smallest string itself.
### What a Strong Answer Covers
- The palindrome requirement and exact preservation of character counts.
- Lexicographic minimality of the returned string.
- Single-character, odd-length, even-length and repeated-letter inputs.
- Time and space bounds for `100000` characters.
### Follow-up Questions
- What additional outcome would need to be specified if the input were not guaranteed to be a palindrome or even rearrangeable into one?
- Is a string consisting of only one repeated letter changed by the requested rearrangement?
```hint Use the symmetry
A palindrome's right half is determined by its left half, and an odd-length palindrome has a fixed middle letter. Determine the available letters for one half, then choose their order to minimize the full string.
```
Overview: Rearrange a lowercase palindrome into its lexicographically smallest palindromic permutation. Preserve repeated character counts and handle odd, even and single-character strings.