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:
num, but you must use at least one digit.
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 <= 105num consists of digits.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.
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.
Python
JavaScript
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.
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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| 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. |
| Two Pointer Merge Technique | Time Complexity: O(n), as the string is traversed to fill the frequency array and to construct the palindrome. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count and Greedy Construction | O(n) | O(1) | Best general solution. Uses digit frequency and greedy pairing for optimal performance. |
| Two Pointer Merge Technique | O(n log n) | O(n) | Useful when digits are already sorted or when implementing pair grouping after sorting. |
LARGEST PALINDROMIC NUMBER | LEETCODE 2384 | PYTHON SOLUTION • Cracking FAANG • 3,307 views views
Watch 9 more video solutions →Practice Largest Palindromic Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor