Least Palindromic Permutation Above a Target
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
You are given lowercase English strings `s` and `target` of the same length.
Return the lexicographically smallest string satisfying all of these requirements:
- It is a permutation of `s`, using every character with its original multiplicity.
- It is a palindrome, reading the same forward and backward.
- It is strictly greater than `target` in lexicographic order.
If no such string exists, return an empty string. For equal-length strings, lexicographic order is determined by the first differing character.
```cpp
class Solution {
public:
string lexPalindromicPermutation(string s, string target);
};
```
### Examples
**Example 1:**
```text
Input: s = "aabb", target = "abaa"
Output: "abba"
Explanation: The palindromic permutations are "abba" and "baab". Both exceed "abaa", and "abba" is smaller.
```
**Example 2:**
```text
Input: s = "aabbc", target = "abcba"
Output: "bacab"
Explanation: The palindromic permutations are "abcba" and "bacab". Equality is not sufficient, so only "bacab" qualifies.
```
### Constraints
- `1 <= s.length == target.length <= 300`.
- Both strings consist only of lowercase English letters.
### Clarifying Questions
- Is `s` guaranteed to have a palindromic permutation? No.
- Must `target` be a palindrome or a permutation of `s`? No.
- May equality with `target` be returned? No; the comparison is strict.
- Can a valid palindrome omit characters? No; the full multiset of `s` must be preserved.
### What a Strong Answer Covers
- Palindromicity, exact character multiplicities, and strict lexicographic comparison together.
- Minimality among all qualifying strings and a complete no-result argument.
- Odd and even lengths, repeated characters, and one-character inputs.
- Resource bounds for the full length limit.
### Follow-up Questions
- How would allowing equality change which outputs are acceptable?
- How could requesting every qualifying palindrome affect output size?
```hint Compare complete palindromes when a half is equal
Character counts determine whether a palindrome is possible and fix its middle character when needed. Construct its first half from half-counts. A larger first half makes the palindrome larger, but an equal first half requires comparing the full mirrored string with target. If equality is insufficient, find the next feasible greater half using reversible character counts.
```
Overview: Find the least palindromic permutation strictly above a target. Covers repeated letters, full-string comparison, impossibility, proof, and C++ code.