For a digit, 
The palindrome cannot have leading zeros. We have a leading zero if pal_half‘s first digit is 0. Since we are processing largest to smallest digits, that can happen in two cases:
numis a string of “0”s. Example:. Our palindrome should be:
.
- There is a single instance of a non-zero digit and all other digits are “0”s. That non-zero digit would be the center. Example:
. Our palindrome should be:
.
Time: 
from heapq import heapify, heappop as pop
class Solution:
def largestPalindromic(self, num: str) -> str:
# Between two plaindromic digit, we should take the larger one
# A pair or a single
# 4 4 4 9 4 7 1 3 7
# 4: 4
# 9: 1
# 7: 2
# 1: 1
# 3: 1
# largest odd is center
# max_heap = (3, 1) (1, 1)
# pal_half = [7 4 4]
# center = 9
count_of = {}
for x in num:
if x not in count_of:
count_of[x] = 1
else:
count_of[x] += 1
max_heap = [(-int(x), count) for x, count in count_of.items()]
heapify(max_heap)
center = -1
pal_half = []
while max_heap:
neg_digit, count = pop(max_heap)
digit = -neg_digit
if digit == 0 and not pal_half:
center = max(center, 0)
continue
q, r = divmod(count, 2)
pal_half += [str(digit)] * q
center = max(center, digit) if r else center
return (
"".join(pal_half)
+ ("" if center < 0 else str(center))
+ "".join(pal_half[::-1])
)
unreasonably effective 
Leave a comment