2384

2384. Largest Palindromic Number (Medium)

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.

Companies: Adobe, Microsoft

Related Topics:
Hash Table, String, Greedy

Similar Questions:

• Longest Palindrome (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/largest-palindromic-number
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    string largestPalindromic(string s) {
        int cnt[10] = {};
        for (char c : s) cnt[c - '0']++;
        string ans;
        for (int i = 9; i >= 0; --i) {
            int c = cnt[i] / 2;
            if (i > 0 || ans.size()) { // avoid adding leading zeros
                while (c-- > 0) ans += '0' + i;
                cnt[i] %= 2;
            }
        }
        int m = 9;
        while (m >= 0 && cnt[m] == 0) --m;
        return ans + (m >= 0 ? string(1, '0' + m) : "") + string(rbegin(ans), rend(ans));
    }
};