Question

2384. Largest Palindromic Number

中文文档

Description

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.

Solutions

Solution 1

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'

class Solution {
  public String largestPalindromic(String num) {
    int[] cnt = new int[10];
    for (char c : num.toCharArray()) {
      ++cnt[c - '0'];
    }
    String mid = "";
    for (int i = 9; i >= 0; --i) {
      if (cnt[i] % 2 == 1) {
        mid += i;
        --cnt[i];
        break;
      }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < 10; ++i) {
      if (cnt[i] > 0) {
        cnt[i] >>= 1;
        sb.append(("" + i).repeat(cnt[i]));
      }
    }
    while (sb.length() > 0 && sb.charAt(sb.length() - 1) == '0') {
      sb.deleteCharAt(sb.length() - 1);
    }
    String t = sb.toString();
    String ans = sb.reverse().toString() + mid + t;
    return "".equals(ans) ? "0" : ans;
  }
}

class Solution {
public:
  string largestPalindromic(string num) {
    vector<int> cnt(10);
    for (char c : num) ++cnt[c - '0'];
    string mid = "";
    for (int i = 9; ~i; --i) {
      if (cnt[i] % 2) {
        mid += (i + '0');
        --cnt[i];
        break;
      }
    }
    string t = "";
    for (int i = 0; i < 10; ++i) {
      if (cnt[i]) {
        cnt[i] >>= 1;
        while (cnt[i]--) {
          t += (i + '0');
        }
      }
    }
    while (t.size() && t.back() == '0') {
      t.pop_back();
    }
    string ans = t;
    reverse(ans.begin(), ans.end());
    ans += mid + t;
    return ans == "" ? "0" : ans;
  }
};

func largestPalindromic(num string) string {
  cnt := make([]int, 10)
  for _, c := range num {
    cnt[c-'0']++
  }
  ans := ""
  for i := 9; i >= 0; i-- {
    if cnt[i]%2 == 1 {
      ans = strconv.Itoa(i)
      cnt[i]--
      break
    }
  }
  for i := 0; i < 10; i++ {
    if cnt[i] > 0 {
      cnt[i] >>= 1
      s := strings.Repeat(strconv.Itoa(i), cnt[i])
      ans = s + ans + s
    }
  }
  ans = strings.Trim(ans, "0")
  if ans == "" {
    return "0"
  }
  return ans
}

function largestPalindromic(num: string): string {
  const count = new Array(10).fill(0);
  for (const c of num) {
    count[c]++;
  }
  while (count.reduce((r, v) => (v % 2 === 1 ? r + 1 : r), 0) > 1) {
    for (let i = 0; i < 10; i++) {
      if (count[i] % 2 === 1) {
        count[i]--;
        break;
      }
    }
  }

  let res = [];
  let oddIndex = -1;
  for (let i = 9; i >= 0; i--) {
    if (count[i] % 2 == 1) {
      oddIndex = i;
      count[i] -= 1;
    }
    res.push(...new Array(count[i] >> 1).fill(i));
  }
  if (oddIndex !== -1) {
    res.push(oddIndex);
  }
  const n = res.length;
  for (let i = 0; i < n; i++) {
    if (res[i] !== 0) {
      res = res.slice(i);
      if (oddIndex !== -1) {
        res.push(...[...res.slice(0, res.length - 1)].reverse());
      } else {
        res.push(...[...res].reverse());
      }
      return res.join('');
    }
  }

  return '0';
}