Largest Palindromic Number — LeetCode 2384 Python Solution

The problem

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.

Example

Input

num = "444947137"

Output

"7449447"

Explanation

Use the digits "4449477" from "444947137" to form the palindromic integer "7449447".

Python solution

class Solution:
    def largestPalindromic(self, num: str) -> str:
        cnt = Counter(num)
        ans = ''
        for i in range(9, -1, -1):
            v = str(i)
            if cnt[v] % 2:
                ans = v
                cnt[v] -= 1
                break
        for i in range(10):
            v = str(i)
            if cnt[v]:
                cnt[v] //= 2
                s = cnt[v] * v
                ans = s + ans + s
        return ans.strip('0') or '0'

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2384. Largest Palindromic Number is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems