Largest Palindromic Number - Video Solutions

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.