Skip to content

2384. Largest Palindromic Number

Difficulty Topics

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

largest-palindromic-number.py
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]