难度: Medium
给你一个仅由数字（0 - 9）组成的字符串 num 。
请你找出能够使用 num 中数字形成的 最大回文 整数，并以字符串形式返回。该整数不含 前导零 。
注意：
num 中的所有数字，但你必须使用 至少 一个数字。示例 1：
输入：num = "444947137" 输出："7449447" 解释： 从 "444947137" 中选用数字 "4449477"，可以形成回文整数 "7449447" 。 可以证明 "7449447" 是能够形成的最大回文整数。
示例 2：
输入：num = "00009" 输出："9" 解释： 可以证明 "9" 能够形成的最大回文整数。 注意返回的整数不应含前导零。
提示：
1 <= num.length <= 105num 由数字（0 - 9）组成运行时间: 45 ms
内存: 16.7 MB
class Solution:
def largestPalindromic(self, num: str) -> str:
c = [num.count(str(i)) for i in range(10)]
e = [x // 2 for x in c]
o = [x % 2 for x in c]
oo = ee = ''
for i in range(9, -1, -1):
if e[i] > 0:
ee += str(i) * e[i]
for i in range(9, -1, -1):
if o[i] > 0:
oo = str(i)
break
if ee.startswith('0') and sum(o)==0:
return '0'
ee = '' if ee.startswith('0') else ee
return ee + oo + ee[::-1]
此题解的思路基于统计输入字符串中每个数字的出现次数。首先，创建一个计数数组c来统计字符串中每个数字的数量。接着，根据每个数字的数量，计算出每个数字可以形成的对数（即最大的偶数次），以及剩余的是否能为中心字符（奇数次的存在）。为构造最大的回文数字，从最大的数字（9）到最小的数字（0）进行遍历，优先使用数字对形成回文的两侧。如果存在奇数次的数字，选择最大的一个作为回文的中心。特别注意，如果所有的偶数部分数字为'0'且没有奇数中心，应直接返回'0'以避免前导零问题。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def largestPalindromic(self, num: str) -> str:
c = [num.count(str(i)) for i in range(10)] # 统计每个数字0-9在num中出现的次数
e = [x // 2 for x in c] # 对于每个数字，计算可以配对的最大对数
o = [x % 2 for x in c] # 对于每个数字，是否有剩余的奇数个数
oo = ee = '' # 初始化最终构造回文的两部分
for i in range(9, -1, -1):
if e[i] > 0: # 如果数字i可以配对，加入到ee
ee += str(i) * e[i]
for i in range(9, -1, -1):
if o[i] > 0: # 找到最大的奇数个数的数字作为中心
oo = str(i)
break
if ee.startswith('0') and sum(o)==0: # 特殊情况：只有0且无中心数字
return '0'
ee = '' if ee.startswith('0') else ee # 避免前导零
return ee + oo + ee[::-1] # 构建回文字符串
在构建最大的回文数字时，选择最大的奇数数字作为中心可以确保生成的回文数值尽可能大。由于回文结构中心的数字只能单独存在，因此使用最大的奇数数字作为中心可以有效地增加整个回文数的数值。例如，如果中心能选择9而选择了1，那么最终的回文数字将显著变小。
如果存在奇数中心但偶数部分全为'0'，则应构建回文数使其只包含这个奇数中心。例如，如果中心是3而偶数部分全为0，则回文数应为'3'。这种情况下，不会有前导零问题，因为只有一个数字构成回文。
从数字9到0逆序添加数字到回文的两端确保了构建的回文数是最大可能的值。因为回文是对称的，所以在每侧从大到小添加相同数量的数字，可以最大化回文数的数值。这种方法保证了在给定数字的限制下，构建的回文数总是最大的。
此方法通常是可靠的，因为如果ee以'0'开头，则意味着所有较大的数字都未能形成对，而只有数字0形成了对。在没有其他数字的情况下，如果ee仅包含'0'，则整个字符串应该只返回'0'，以避免前导零问题。这种情况下，检查是否以'0'开头足以判断是否需要返回'0'，因此不会发生误判。