Problem 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
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.
Approach
Since the integers can be fully reordered, the intuition (and practically the correct approach) is to start off with the largest digits and place them towards the edge of the result. For example, we would prefer "9119", compared to "1991".
We can keep track of the counts using a hash map, through the form of a defaultdict. then, we can take care of the leading zeros, by placing them at the very center. One last thing is the take care of the center digit (if it exists), completed in both cases on whether its a zero or a non-zero integer.
Had a hard time figuring out the edge cases, but overall a simple greedy approach works for the problem.+
Solution
from collections import defaultdict
class Solution(object):
def largestPalindromic(self, num):
result = ""
numcnt = defaultdict(int)
for char in num:
numcnt[char] += 1
center = ""
for i in "123456789":
while numcnt[i] > 1:
numcnt[i] -= 2
result = i + result
if numcnt[i] == 1:
center = i
numcnt[i] = 0
while numcnt['0'] >= 2 and len(result) > 0:
result += '0'
numcnt['0'] -= 2
if numcnt['0'] == 1 and center == "":
center = '0'
if result == "" and center == "":
return '0'
return result + center + result[::-1]