<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:
        d = dict()
        for i in range(len(num)):
            if(d.get(num[i])==None):
                d.update({num[i]:1})
            else:
                d[num[i]]+=1
        
        
        oddNo = '-1'
        l = []
        for i,j in d.items():
            if(j%2==0):
                l.append(i*j)
            else:
                if(int(oddNo)<int(i)):
                        oddNo = i
                if(j!=1):
                    l.append(i*(j-1))
            
        l.sort()
        x = ''
        for i in range(len(l)):
            if(i==0 and oddNo!='-1'):
                x = l[i][:len(l[i])//2]+oddNo+l[i][len(l[i])//2:]
            else:
                x = l[i][:len(l[i])//2]+x+l[i][len(l[i])//2:]

        if(x==''):
            if(oddNo!='-1'):
                return oddNo
            else:
                return ''
        
        if(x[0]=='0'):
            cnt = 0
            for i in range(len(x)):
                if(x[i]!='0'):
                    x = x[cnt:]
                    x = x[:-cnt]
                    break
                else:
                    cnt+=1

            if(cnt==len(x) and x[0]=='0'):
                return '0'
        return x

        
18100