<p>You are given a string <code>num</code> consisting of digits only.</p>

<p>Return <em>the <strong>largest palindromic</strong> integer (in the form of a string) that can be formed using digits taken from </em><code>num</code>. It should not contain <strong>leading zeroes</strong>.</p>

<p><strong>Notes:</strong></p>

<ul>
	<li>You do <strong>not</strong> need to use all the digits of <code>num</code>, but you must use <strong>at least</strong> one digit.</li>
	<li>The digits can be reordered.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;444947137&quot;
<strong>Output:</strong> &quot;7449447&quot;
<strong>Explanation:</strong> 
Use the digits &quot;4449477&quot; from &quot;<u><strong>44494</strong></u><u><strong>7</strong></u>13<u><strong>7</strong></u>&quot; to form the palindromic integer &quot;7449447&quot;.
It can be shown that &quot;7449447&quot; is the largest palindromic integer that can be formed.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;00009&quot;
<strong>Output:</strong> &quot;9&quot;
<strong>Explanation:</strong> 
It can be shown that &quot;9&quot; is the largest palindromic integer that can be formed.
Note that the integer returned should not contain leading zeroes.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num.length &lt;= 10<sup>5</sup></code></li>
	<li><code>num</code> consists of digits.</li>
</ul>

from collections import defaultdict
class Solution:
    # Method: Hash -> T = O(n)
    def largestPalindromic(self, num: str) -> str:
        pal = []
        if not num: return pal
        
        # step_1: create a dict to count the freq of each digit 
        digit_cnt = defaultdict(int)
        for digit in num:
            digit_cnt[digit] += 1
        
        # step_2: iteration digits in decreasing order
        digits = [str(x) for x in range(9, -1, -1)]
        for digit in digits:
            cnt = digit_cnt[digit]
            
            n = len(pal)
            if n % 2 == 0:
                pal = pal[: n//2] + [digit] * cnt + pal[n//2 :]
            else:
                if digit == '0':
                    if n != 1:
                        pal = pal[:n // 2] + ['0'] * (cnt // 2) + [pal[n // 2]] + ['0'] * (cnt // 2) + pal[n // 2 + 1:]
                else:
                    if cnt >= 2:
                        pal = pal[:n // 2] + [digit] * (cnt // 2) + [pal[n // 2]] + [digit] * (cnt // 2) + pal[n // 2 + 1:]
        
        # step_3: output 
        res = ''.join(pal).lstrip('0')
        return res if res else '0'




19600