2384-最大回文数字

给你一个仅由数字（0 - 9）组成的字符串 num 。

请你找出能够使用 num 中数字形成的 最大回文 整数，并以字符串形式返回。该整数不含 前导零 。

注意：

• 你 无需 使用 num 中的所有数字，但你必须使用 至少 一个数字。
• 数字可以重新排序。

示例 1：

**输入：** num = "444947137"
**输出：** "7449447"
**解释：**
从 " _ **44494**_ _ **7**_ 13 _ **7**_ " 中选用数字 "4449477"，可以形成回文整数 "7449447" 。
可以证明 "7449447" 是能够形成的最大回文整数。

示例 2：

**输入：** num = "00009"
**输出：** "9"
**解释：**
可以证明 "9" 能够形成的最大回文整数。
注意返回的整数不应含前导零。

提示：

• 1 <= num.length <= 105
• num 由数字（0 - 9）组成

解法：贪心

一个回文串（如 998767899，123321）可以被分成两部分：

• 两边对应的部分（如 9987 和 7899，123 和 321），这两部分中的数字每种都出现偶数次。
• 中间单独一个数字（如 6），这部分是可选的。

因此令 cnt[i] 表示数字 i 出现的次数，我们先从 9 到 0 枚举第一部分中出现的数，再看是否还有剩下的数放进中间单独的数字即可。复杂度 \mathcal{O}(n)。

由于题目要求不能有前导零，因此本题有一定实现细节，详见参考代码的注释。

参考代码（c++）

class Solution {
public:
    string largestPalindromic(string num) {
        int cnt[10] = {0};
        for (char c : num) cnt[c - '0']++;
        // ans 表示对应的部分中的前一半，ans2 是 ans 的倒序
        string ans, ans2;
        // 求回文串两边对应的部分
        for (int i = 9; i >= 0; i--) {
            // 已经枚举到了 0，但是之前从来没有加入过别的数字。此时加入 0 将会导致前导 0，因此直接结束。
            if (i == 0 && ans.empty()) break;
            // 在这部分中出现过的数必须出现偶数次
            int t = cnt[i] / 2;
            for (int j = 0; j < t; j++) ans.push_back(i + '0');
            cnt[i] -= t * 2;
        }
        ans2 = ans;
        reverse(ans2.begin(), ans2.end());
        // 看看是否还有剩下的数，可以作为中间单独的一个数字
        for (int i = 9; i >= 0; i--) if (cnt[i]) {
            // 此时 0 无需跳过，因为单独一个 0 是合法的答案
            ans.push_back(i + '0');
            break;
        }
        return ans + ans2;
    }
};