2384. Largest Palindromic Number

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  string largestPalindromic(string num) {
    unordered_map<char, int> 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<char, int>& 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 == string::npos ? "" : firstHalf.substr(index);
  }

  string getMid(const unordered_map<char, int>& 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 % 2 == 1)
        return string(1, c);
    }
    return "";
  }

  string reversed(const string& s) {
    return {s.rbegin(), s.rend()};
  }
};

class Solution {
  public String largestPalindromic(String num) {
    Map<Character, Integer> 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<Character, Integer> 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<Character, Integer> 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();
  }
}

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 ''