Is Largest Palindromic Number easy or hard?

Largest Palindromic Number is rated Medium difficulty on LeetCode with an acceptance rate around 37%. The challenge lies in constructing the largest numeric palindrome while handling edge cases such as leading zeros and choosing the correct center digit.

Largest Palindromic Number Python/Java solution

Python and JavaScript implementations typically use a frequency counter and string builder to construct the left half, select a middle digit, and mirror the result. Java and C# solutions often use sorted arrays with two-pointer grouping or the same counting strategy.

How to solve Largest Palindromic Number in O(n)?

Use a counting approach. Create a frequency array for digits 0–9, then greedily append digit pairs from 9 down to 0 to form the left half of the palindrome. Select the largest remaining digit as the middle if one exists, and mirror the left half to complete the palindrome. Skip leading zero pairs unless the result would otherwise be empty.

What is the best approach for Largest Palindromic Number?

The frequency count with greedy construction is the optimal approach. Count occurrences of each digit, add pairs of digits from 9 down to 0 to build the left half, and mirror it. If a digit remains unpaired, place the largest one in the center. This method runs in O(n) time with O(1) space because only digits 0–9 are tracked.

Is Largest Palindromic Number asked at Google/Amazon/Meta?

Palindrome construction and greedy digit problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants involving digit rearrangement, counting frequencies, or building palindromes are common because they test greedy reasoning and string manipulation.

What data structure is used in Largest Palindromic Number?

A frequency array or hash table is the primary data structure. It stores how many times each digit appears, enabling efficient pairing of digits when constructing the palindrome. Strings or character arrays are then used to build the final result.

What is the time complexity of Largest Palindromic Number?

The optimal solution runs in O(n) time where n is the length of the digit string. Counting frequencies takes one pass and constructing the palindrome requires iterating through digits 0–9. Space complexity is O(1) because the frequency array size is constant.

Description Hints 4 Solution Video 14:56

2384. Largest Palindromic Number

Medium37.1% acceptance3 companies

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

Asked at 3 companies

Geico Microsoft Amazon

Topics

Hints open one at a time

Hint 1

In order to form a valid palindrome, other than the middle digit in an odd-length palindrome, every digit needs to exist on both sides.

Hint 2

A longer palindrome implies a larger valued palindrome. For palindromes of the same length, the larger digits should occur first.

Hint 3

We can count the occurrences of each digit and build the palindrome starting from the ends. Starting from the larger digits, if there are still at least 2 occurrences of a digit, we can place these digits on each side.

Hint 4

Make sure to consider the special case for the center digit (if any) and zeroes. There should not be leading zeroes.

14:56

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution