Build the Greatest Non-Leading-Zero Palindrome from Available Digits
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Choose at least one digit occurrence from string `num`, leaving others unused if you wish. Rearrange the chosen digits into a palindrome and return the numerically greatest possible result as a string. The result must have no leading zeroes, except for the single-digit number `"0"`.
```cpp
class Solution {
public:
string largestPalindromic(string num);
};
```
### Examples
**Example 1:**
```text
Input: num = "112200"
Output: "210012"
Explanation: Use all six digits, with left half "210" and its mirror "012", giving the largest six-digit palindrome.
```
**Example 2:**
```text
Input: num = "0007"
Output: "7"
Explanation: No nonzero pair can enclose zeroes without a leading zero. The greatest available single digit is 7.
```
### Constraints
- `1 <= num.length <= 100000`.
- num contains decimal digits only.
### Clarifying Questions
- Must all digits be used? No, but at least one must be used.
- Can digits be reordered? Yes.
- Can an occurrence be used twice? No.
- What if every digit is zero? Return `"0"`.
```hint Check the boundary
Compare a single zero with a multidigit string that starts with zero.
```
Overview: Build the greatest palindromic integer from available digit occurrences, allowing unused digits and forbidding leading zeroes.
