Skip to main content
Talentd

Largest Palindromic Number - Solution & Explanation

MediumHash TableStringGreedyCounting10 min readAsked at: Amazon, Microsoft, Geico
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given a string of digits. Rearrange some or all digits to form the numerically largest palindromic number. Each digit can be used at most as many times as it appears in the input, and the result cannot contain leading zeros unless the entire palindrome is "0".

Approach 1: Frequency Count and Greedy Construction (Time: O(n), Space: O(1))

This approach counts how many times each digit appears, then greedily builds the palindrome from the largest digits down. Use a frequency array or map (a classic Hash Table / Counting technique) to track occurrences of digits 0–9. For every digit from 9 to 0, place count[d] / 2 copies on the left side of the palindrome. These will later be mirrored to the right side. If any digit still has one leftover occurrence, choose the largest such digit as the middle character.

The key constraint is avoiding leading zeros. If the current left half is empty, skip adding pairs of '0'. This prevents results like "000..." when larger digits exist. After building the left half, mirror it and insert the chosen middle digit if one exists. This greedy ordering ensures the final palindrome is numerically maximal. Because the digit range is fixed (0–9), counting and construction run in linear time with constant auxiliary space.

Approach 2: Two Pointer Merge Technique (Time: O(n log n), Space: O(n))

This method first sorts the digits so larger values are processed earlier. After sorting, use a two pointers style merge strategy: one pointer scans from the start while another groups identical digits from the end. Whenever a pair of the same digit is found, append one to the left half and reserve the other for the mirrored side. Digits without pairs are candidates for the center position of the palindrome.

Sorting simplifies grouping but increases time complexity to O(n log n). After pairing digits, track the largest unpaired digit to place in the middle. Finally concatenate left + middle + reverse(left). This approach is straightforward in languages where sorting strings or arrays is convenient, though it uses extra memory for the sorted structure.

Recommended for interviews: The frequency-count greedy solution is what most interviewers expect. It shows you recognize the fixed digit range and can exploit counting for linear performance. Explaining the pairing logic and the rule that prevents leading zeros demonstrates strong understanding of Greedy construction and palindrome structure.

Approach 1: Frequency Count and Greedy Construction

This approach involves counting the frequency of each digit in the string. We then determine the maximum possible digits that can form the palindromic structure by utilizing greedy principles. The highest digits available will be used to maximize the number, ensuring no leading zeroes.

The function begins by counting all digits in the given number string. It then collects pairs of digits to form the left and right halves of the palindrome. The 'middle' is the largest possible digit that can appear in the center if any single digit remains unpaired. The result string is formed by joining the left-half, the middle digit, and the inverse of the left-half. Leading zeroes are avoided by skipping over zeros when left-half is empty.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the input string. We traverse the input once to count, then traverse a fixed range of 10 to construct the palindrome.
Space Complexity: O(1), apart from the output, because the frequency array size and other variables do not depend on input size.

Try this approach in the editor →

Approach 2: Two Pointer Merge Technique

We use a two-pointer approach to sort and find the largest palindromic number. By sorting the digits in descending order, palindromic sequences are attempted from both ends, ensuring to skip zeroes to avoid leading zeros.

This Java implementation uses a frequency array to count each digit. We form the palindrome by attempting to build a string from the highest digits while maintaining symmetry using a two-pointer mechanism. The largest unused digit may be placed in the middle if possible. Forming the output ensures no leading zeros are present by skipping initial zeros.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n), as the string is traversed to fill the frequency array and to construct the palindrome.
Space Complexity: O(1), extra space use is minimal and constant.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Frequency Count and Greedy Construction

Time Complexity: O(n) where n is the length of the input string. We traverse the input once to count, then traverse a fixed range of 10 to construct the palindrome.
Space Complexity: O(1), apart from the output, because the frequency array size and other variables do not depend on input size.

Two Pointer Merge Technique

Time Complexity: O(n), as the string is traversed to fill the frequency array and to construct the palindrome.
Space Complexity: O(1), extra space use is minimal and constant.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Count and Greedy ConstructionO(n)O(1)Best general solution. Uses digit frequency and greedy pairing for optimal performance.
Two Pointer Merge TechniqueO(n log n)O(n)Useful when digits are already sorted or when implementing pair grouping after sorting.

Video Solution

LARGEST PALINDROMIC NUMBER | LEETCODE 2384 | PYTHON SOLUTION • Cracking FAANG • 3,419 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Largest Palindromic Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindrome