< Back





2384. Largest Palindromic Number

Given a string of numbers, we're asked to find the longest palindromic number that can be created,
with no leading "0" characters. What we know about palindromes is that the string needs to be the
same, forward and reverse. At least one of the numbers in the original input will be in the middle,
if it appears in the original string an odd numebr of times.

Given the task ahead of us, we'll tackle it greedily. We want to prioritize the largest numbers
first at the beginning of the new string, and the smallest numbers in the center - except for the
middle. If a middle is present in the original string (an integer that appears an odd number of
times), we'll chose the largest of these middle options.

We count the occurence of every integer in the original string, sort them, and process them from
largest to smallest. We maintain a middle which is the maximum number seen an odd number of times.
For each integer in the input, we add to our first half of the string half of the occurrences of the
integer in the original string.

Finally, we strip off all leading zeros and then construct the answer - the first half in decreasing
order, the middle, and the last half reversed. If the ans is "" we return "0", otherwise we return
the largest palindromic number from the input.

The solution is as follows:


  from collections import Counter

  class Solution:
      def largestPalindromic(self, num: str) -> str:
          count = Counter(num)
          ans = m = ""

          for char in sorted(count.keys(), reverse=True):
              m = max(m, char * (count[char] & 1))
              ans += char * (count[char] // 2)

          ans = ans.lstrip("0")
          ans = ans + m + ans[::-1]
          return ans if ans else "0"


_ Time Complexity:

  O(n log n) - We count and sort the input.

_ Space Complexity:

  O(n) - We maintain strings to construct the final answer.