# 2384. Largest Palindromic Number

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { public: string largestPalindromic(string num) { unordered_map count; for (const char c : num) ++count[c]; const string firstHalf = getFirstHalf(count); const string mid = getMid(count); const string ans = firstHalf + mid + reversed(firstHalf); return ans.empty() ? "0" : ans; } private: string getFirstHalf(const unordered_map& count) { string firstHalf; for (char c = '9'; c >= '0'; --c) { const auto it = count.find(c); if (it == count.cend()) continue; const int freq = it->second; firstHalf += string(freq / 2, c); } const int index = firstHalf.find_first_not_of('0'); return index == -1 ? "" : firstHalf.substr(index); } string getMid(const unordered_map& count) { for (char c = '9'; c >= '0'; --c) { const auto it = count.find(c); if (it == count.cend()) continue; const int freq = it->second; if (freq & 1) return string(1, c); } return ""; } string reversed(const string& s) { return {s.rbegin(), s.rend()}; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { public String largestPalindromic(String num) { Map count = new HashMap<>(); for (final char c : num.toCharArray()) count.merge(c, 1, Integer::sum); final String firstHalf = getFirstHalf(count); final String mid = getMid(count); final String ans = firstHalf + mid + reversed(firstHalf); return ans.isEmpty() ? "0" : ans; } private String getFirstHalf(Map count) { StringBuilder sb = new StringBuilder(); for (char c = '9'; c >= '0'; --c) { final int freq = count.getOrDefault(c, 0); sb.append(String.valueOf(c).repeat(freq / 2)); } final int index = firstNotZeroIndex(sb); return index == -1 ? "" : sb.substring(index); } private int firstNotZeroIndex(StringBuilder sb) { for (int i = 0; i < sb.length(); ++i) if (sb.charAt(i) != '0') return i; return -1; } private String getMid(Map count) { StringBuilder sb = new StringBuilder(); for (char c = '9'; c >= '0'; --c) { final int freq = count.getOrDefault(c, 0); if (freq % 2 == 1) return String.valueOf(c); } return ""; } private String reversed(final String s) { return new StringBuilder(s).reverse().toString(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def largestPalindromic(self, num: str) -> str: count = collections.Counter(num) firstHalf = ''.join(count[i] // 2 * i for i in '9876543210').lstrip('0') mid = self._getMid(count) return (firstHalf + mid + firstHalf[::-1]) or '0' def _getMid(self, count: Dict[str, int]) -> str: for c in '9876543210': if count[c] & 1: return c return ''