Largest Palindromic Number

Medium
1238.

Largest Palindromic Number

Largest Palindromic Number is a medium coding problem on strings, hash table and greedy, asked in Amazon and Google interviews.

You are given a string num of digits. Choose some of its digits — at least one — and rearrange them in any order to form a palindromic integer (it reads the same forwards and backwards).

The result must not have leading zeros, so "0" is allowed but "00" and "0110" are not. Each character of num may be used at most once.

Return the largest palindromic integer you can form, as a string.

Example 1

Input
num = "2026"
Output
262
Explanation
The pair of `2`s goes on the outside and `6` beats `0` for the middle.

Example 2

Input
num = "9911000"
Output
9100019

Example 3

Input
num = "00009"
Output
9
Explanation
`"90009"` is impossible with one `9`, and `"00900"` has leading zeros.

Constraints

  • 1 <= num.length <= 10^5
  • num consists of digits
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} num
 * @return {string}
 */
var largestPalindromic = function(num) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Largest Palindromic Number — Solution in Python, Java & C++

Largest Palindromic Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Largest Palindromic Number is a medium coding problem on strings, hash table and greedy, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Greedy, Counting
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string num of digits. Choose some of its digits — at least one — and rearrange them in any order to form a palindromic integer (it reads the same forwards and backwards).

The result must not have leading zeros, so "0" is allowed but "00" and "0110" are not. Each character of num may be used at most once.

Return the largest palindromic integer you can form, as a string.

Example 1

Input: num = "2026"
Output: 262
Explanation: The pair of `2`s goes on the outside and `6` beats `0` for the middle.

Example 2

Input: num = "9911000"
Output: 9100019

Example 3

Input: num = "00009"
Output: 9
Explanation: `"90009"` is impossible with one `9`, and `"00900"` has leading zeros.

Constraints

  • 1 <= num.length <= 10^5
  • num consists of digits

Hints for Largest Palindromic Number

  1. Hint 1

    A palindrome is a sequence of mirrored pairs plus at most one unpaired middle digit.

  2. Hint 2

    Longer is larger. Use as many pairs as you can, biggest digits on the outside.

  3. Hint 3

    Watch out for zeros: if the only pairs available are 0 pairs, they would lead the number — drop them. Then put the largest leftover digit in the middle; if nothing at all is left, the answer is "0".

How to solve Largest Palindromic Number

Count the digits. The left half takes cnt[d] / 2 copies of each digit from 9 down to 0, the middle takes the largest digit with a copy left over — unless the half would start with 0, in which case the half is dropped entirely.

Approach

  1. Count each digit of num.
  2. Build left by appending digit d exactly cnt[d] / 2 times for d from 9 down to 0.
  3. If left starts with 0, it is made of zeros only; set it to the empty string.
  4. Let mid be the largest digit whose count is odd (empty if none).
  5. If both left and mid are empty, return "0"; otherwise return left + mid + reverse(left).

Why it works

A longer number without leading zeros is always larger, so we want as many digits as possible: every available pair, plus a centre if any digit has a copy left. Among palindromes of the same length the largest puts the largest digits outermost, which is the descending left half. The only conflict is with leading zeros: if the outermost pair would be 0, every pair is a 0 pair, and none of them can be used. After dropping them, every non-zero digit present appears exactly once, so the best we can do is the largest single digit, or "0" when only zeros were given.

Complexity

  • Time — O(n)
  • Space — O(n) for the output

Pitfalls

  • Dropping the zero pairs only applies when the half starts with 0; zeros inside a half that starts with a non-zero digit are fine (9100019).
  • num = "00" must return "0", not an empty string.
  • The middle digit is the largest one with an odd count, which may be 0.

Reference solution

Python

def largestPalindromic(num: str) -> str:
    cnt = [0] * 10
    for ch in num:
        cnt[ord(ch) - 48] += 1
    left = "".join(str(d) * (cnt[d] // 2) for d in range(9, -1, -1))
    if left.startswith("0"):
        left = ""
    mid = ""
    for d in range(9, -1, -1):
        if cnt[d] % 2 == 1:
            mid = str(d)
            break
    if left == "" and mid == "":
        return "0"
    return left + mid + left[::-1]

Java

public static String largestPalindromic(String num) {
    int[] cnt = new int[10];
    for (int i = 0; i < num.length(); i++) cnt[num.charAt(i) - '0']++;
    StringBuilder left = new StringBuilder();
    for (int d = 9; d >= 0; d--) for (int k = 0; k < cnt[d] / 2; k++) left.append((char) ('0' + d));
    if (left.length() > 0 && left.charAt(0) == '0') left.setLength(0);
    String mid = "";
    for (int d = 9; d >= 0; d--) if (cnt[d] % 2 == 1) { mid = String.valueOf((char) ('0' + d)); break; }
    if (left.length() == 0 && mid.isEmpty()) return "0";
    String l = left.toString();
    return l + mid + left.reverse().toString();
}

C++

string largestPalindromic(string num) {
    int cnt[10] = {0};
    for (char ch : num) cnt[ch - '0']++;
    string left;
    for (int d = 9; d >= 0; d--) left += string(cnt[d] / 2, (char)('0' + d));
    if (!left.empty() && left[0] == '0') left = "";
    string mid;
    for (int d = 9; d >= 0; d--) if (cnt[d] % 2 == 1) { mid = string(1, (char)('0' + d)); break; }
    if (left.empty() && mid.empty()) return "0";
    string right(left.rbegin(), left.rend());
    return left + mid + right;
}

JavaScript

var largestPalindromic = function(num) {
    var cnt = new Array(10).fill(0);
    for (var i = 0; i < num.length; i++) cnt[num.charCodeAt(i) - 48]++;
    var left = "";
    for (var d = 9; d >= 0; d--) for (var k = 0; k < Math.floor(cnt[d] / 2); k++) left += String(d);
    if (left.length > 0 && left[0] === "0") left = "";
    var mid = "";
    for (var e = 9; e >= 0; e--) if (cnt[e] % 2 === 1) { mid = String(e); break; }
    if (left === "" && mid === "") return "0";
    return left + mid + left.split("").reverse().join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets