<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:
        '''
        find all nums that occur 2+ time
        first get count of all nums and create max heap for nums (looking for max possible num) , 
        then use counts hashmap to count of the max num - if even count -> utilize in answer , if odd
        see if just once -> then utilize as middle , if > 1 , still use as middle.
        '''

        countsMap = {}
        maxHeap = [] # -9 , -7 , -3 
        # 3 7 9
        for char in num:
            if int(char) in countsMap:
                countsMap[int(char)] += 1
            else:
                countsMap[int(char)] = 1
                heapq.heappush(maxHeap, int(char) * -1)
        

        frontHalf = ""
        backHalf = ""
        maxNum = float('-inf')
        # 000099
        # 00
        # 00

        # start at max and work way down.
        while maxHeap:
            num = -1 * heapq.heappop(maxHeap)
            if num in countsMap and countsMap[num] >= 2:
                count = countsMap[num]
                if frontHalf == "" and num == 0:
                    # check if maxNum is 0 or not.
                    if maxNum == float('-inf'):
                        frontHalf = "0"
                    
                    continue
                
                frontHalf+= str(num)*(count//2)
                backHalf = str(num)*(count//2) + backHalf
            if countsMap[num] % 2:
                maxNum = max(maxNum, num)


        return frontHalf + str(maxNum) + backHalf if maxNum != float('-inf') else frontHalf + backHalf

18100