2384. Largest Palindromic Number

Problem Link

Description

---

You are given a string num consisting of digits only.

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

Notes:

• You do not need to use all the digits of num, but you must use at least one digit.
• The digits can be reordered.

 

Example 1:

Input: num = "444947137"
Output: "7449447"
Explanation: 
Use the digits "4449477" from "444947137" to form the palindromic integer "7449447".
It can be shown that "7449447" is the largest palindromic integer that can be formed.

Example 2:

Input: num = "00009"
Output: "9"
Explanation: 
It can be shown that "9" is the largest palindromic integer that can be formed.
Note that the integer returned should not contain leading zeroes.

 

Constraints:

• 1 <= num.length <= 105
• num consists of digits.

Solution

---

Python3

class Solution:
    def largestPalindromic(self, num: str) -> str:
        counter = Counter(num)
        even = []
        odd = -1
        
        for k, v in counter.items():
            if v % 2 == 0:
                even.append((k, v))
            elif v >= 3 and v % 2 == 1:
                even.append((k, v - 1))
                odd = max(odd, int(k))
            elif v == 1:
                odd = max(odd, int(k))
 
        if len(even) == 1 and even[0][0] == "0":
            if odd == -1:
                return "0"
            
            return str(odd)
        
        even.sort(key = lambda x : (-int(x[0])))
        
        part = ""
 
        mid = "" if odd == -1 else str(odd)
        
        for k, v in even:
            part += k * (v // 2)
 
        return part + mid + part[::-1]