<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>

class Solution:
    def largestPalindromic(self, num: str) -> str:
        # two cases:
        # even number
        # 4 -> 4
        # 9 -> 1
        # 7 -> 2
        # 3 -> 1
        # 1 -> 1
        # odd number

        # 8 -> 4
        # 7 -> 6
        # 5 -> 1
        # 2 -> 2
        # 1 -> 5

        # select 
        

        # 8877752115112577788

        # if you take 0 then you have to have another number that is even
        freq = Counter(num)
        freq = dict(reversed(sorted(freq.items())))
        
        if len(freq.items()) == 1 and '0' in freq:
            return "0"
        first_half = []
        second_half = []
        can_use_zero = False
        for digit, frequency in freq.items():
            if digit != '0' and frequency > 1:
                can_use_zero = True
            
            if digit != '0' or (can_use_zero):
                times = frequency // 2
                first_half.extend([digit for _ in range(times)])
                second_half.extend([digit for _ in range(times)])
                freq[digit] -= (2 * times)
        
        for digit, frequency in freq.items():
            if frequency == 1:
                first_half.append(digit)
                break
        
        first_half.extend(list(reversed(second_half)))
        return ''.join(first_half)


                
        


19400