Largest Palindromic Number

Problem

You are given a string num consisting of digits only.

Return _thelargest 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.

Examples

Example 1

1
2
3
4
5


Input: num = "444947137"
Output: "7449447"
Explanation: 
Use the digits "4449477" from "_**44494**_ _**7**_ 13 _**7**_ " to form the palindromic integer "7449447".
It can be shown that "7449447" is the largest palindromic integer that can be formed.

Example 2

1
2
3
4
5


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 <= 10^5
num consists of digits.

Solution

Method 1 – Greedy Counting and Construction

Intuition

To form the largest palindromic number, use the largest available digits for the outer pairs and, if possible, the largest remaining digit for the center. Avoid leading zeros unless the answer is just “0”.

Approach

Count the frequency of each digit in num.
For digits 9 to 0, use as many pairs as possible for the left and right sides.
For the center, use the largest digit with an odd count (if any).
Construct the palindrome by concatenating the left part, center (if any), and the reverse of the left part.
Remove leading zeros unless the result is “0”.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
public:
    string largestPalindromic(string num) {
        vector<int> cnt(10);
        for (char c : num) cnt[c-'0']++;
        string left = "";
        for (int d = 9; d >= 0; --d) {
            int pairs = cnt[d] / 2;
            left += string(pairs, '0'+d);
            cnt[d] -= 2*pairs;
        }
        string center = "";
        for (int d = 9; d >= 0; --d) if (cnt[d]) { center = string(1, '0'+d); break; }
        string res = left;
        reverse(left.begin(), left.end());
        res += center + left;
        int i = 0;
        while (i < res.size()-1 && res[i] == '0') ++i;
        return res.substr(i);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func largestPalindromic(num string) string {
    cnt := make([]int, 10)
    for _, c := range num { cnt[c-'0']++ }
    left := ""
    for d := 9; d >= 0; d-- {
        pairs := cnt[d] / 2
        left += strings.Repeat(string('0'+d), pairs)
        cnt[d] -= 2*pairs
    }
    center := ""
    for d := 9; d >= 0; d-- {
        if cnt[d] > 0 { center = string('0'+d); break }
    }
    res := left + center + reverse(left)
    i := 0
    for i < len(res)-1 && res[i] == '0' { i++ }
    return res[i:]
}
func reverse(s string) string {
    b := []byte(s)
    for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 { b[i], b[j] = b[j], b[i] }
    return string(b)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    public String largestPalindromic(String num) {
        int[] cnt = new int[10];
        for (char c : num.toCharArray()) cnt[c-'0']++;
        StringBuilder left = new StringBuilder();
        for (int d = 9; d >= 0; --d) {
            int pairs = cnt[d] / 2;
            for (int i = 0; i < pairs; ++i) left.append((char)('0'+d));
            cnt[d] -= 2*pairs;
        }
        String center = "";
        for (int d = 9; d >= 0; --d) if (cnt[d] > 0) { center = "" + (char)('0'+d); break; }
        String res = left.toString() + center + left.reverse().toString();
        int i = 0;
        while (i < res.length()-1 && res.charAt(i) == '0') i++;
        return res.substring(i);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    fun largestPalindromic(num: String): String {
        val cnt = IntArray(10)
        for (c in num) cnt[c-'0']++
        val left = StringBuilder()
        for (d in 9 downTo 0) {
            val pairs = cnt[d] / 2
            repeat(pairs) { left.append('0'+d) }
            cnt[d] -= 2*pairs
        }
        var center = ""
        for (d in 9 downTo 0) if (cnt[d] > 0) { center = ("" + ('0'+d).toChar()); break }
        val res = left.toString() + center + left.reverse().toString()
        var i = 0
        while (i < res.length-1 && res[i] == '0') i++
        return res.substring(i)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def largestPalindromic(self, num: str) -> str:
        from collections import Counter
        cnt = Counter(map(int, num))
        left = []
        for d in range(9, -1, -1):
            pairs = cnt[d] // 2
            left.extend([str(d)] * pairs)
            cnt[d] -= 2 * pairs
        center = ''
        for d in range(9, -1, -1):
            if cnt[d]:
                center = str(d)
                break
        res = ''.join(left) + center + ''.join(reversed(left))
        i = 0
        while i < len(res)-1 and res[i] == '0':
            i += 1
        return res[i:]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


impl Solution {
    pub fn largest_palindromic(num: String) -> String {
        let mut cnt = [0; 10];
        for b in num.bytes() { cnt[(b-b'0') as usize] += 1; }
        let mut left = Vec::new();
        for d in (0..=9).rev() {
            let pairs = cnt[d] / 2;
            for _ in 0..pairs { left.push((b'0'+d as u8) as char); }
            cnt[d] -= 2*pairs;
        }
        let mut center = None;
        for d in (0..=9).rev() { if cnt[d] > 0 { center = Some((b'0'+d as u8) as char); break; } }
        let mut res = left.clone();
        if let Some(c) = center { res.push(c); }
        res.extend(left.iter().rev());
        let s: String = res.into_iter().collect();
        let i = s.chars().take_while(|&c| c == '0').count();
        s[i..].to_string()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    largestPalindromic(num: string): string {
        const cnt = Array(10).fill(0)
        for (const c of num) cnt[+c]++
        let left = ''
        for (let d = 9; d >= 0; --d) {
            const pairs = Math.floor(cnt[d]/2)
            left += String(d).repeat(pairs)
            cnt[d] -= 2*pairs
        }
        let center = ''
        for (let d = 9; d >= 0; --d) if (cnt[d]) { center = String(d); break }
        const res = left + center + left.split('').reverse().join('')
        let i = 0
        while (i < res.length-1 && res[i] === '0') i++
        return res.slice(i)
    }
}

Complexity

⏰ Time complexity: O(n), where n is the length of num. Counting and construction are linear.
🧺 Space complexity: O(n), for the result and counts.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Greedy Counting and Construction#

Intuition#

Approach#

Code#

Complexity#