##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2384.html

# 2384. Largest Palindromic Number

• Difficulty: Medium.
• Related Topics: Hash Table, String, Greedy.
• Similar Questions: Longest Palindrome.

## 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. 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.

## Solution (Java, C++, Python)

• class Solution {
public String largestPalindromic(String num) {
int[] count = new int[10];
int center = -1;
StringBuilder first = new StringBuilder();
StringBuilder second;
for (char c : num.toCharArray()) {
count[c - '0']++;
}
int c = 0;
for (int i = 9; i >= 0; i--) {
c = 0;
if (count[i] % 2 == 1 && center == -1) {
center = i;
}
if (first.length() == 0 && i == 0) {
continue;
}
while (c < count[i] / 2) {
first.append(String.valueOf(i));
c++;
}
}
second = new StringBuilder(first.toString());
if (center != -1) {
first.append(center);
}
first.append(second.reverse().toString());
return first.length() == 0 ? "0" : first.toString();
}
}

############

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

############

# 2384. Largest Palindromic Number
# https://leetcode.com/problems/largest-palindromic-number/

class Solution:
def largestPalindromic(self, num: str) -> str:
counter = Counter(num)
even = []
odd = -1

for k, v in counter.items():
if v % 2 == 0:
even.append((k, v))
elif v >= 3 and v % 2 == 1:
even.append((k, v - 1))
odd = max(odd, int(k))
elif v == 1:
odd = max(odd, int(k))

if len(even) == 1 and even[0][0] == "0":
if odd == -1:
return "0"

return str(odd)

even.sort(key = lambda x : (-int(x[0])))

part = ""

mid = "" if odd == -1 else str(odd)

for k, v in even:
part += k * (v // 2)

return part + mid + part[::-1]


• 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';
}



Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).