# Solution: Largest Palindromic Number

Let’s solve the Largest Palindromic Number problem using the Greedy pattern.

## We'll cover the following

## Statement

You are given a string `num`

consisting of digits from `num`

. The resulting palindromic number must not have **leading zeros**.

Note:You may reorder the digits freely, and you must use at least one digit from the`num`

string.

**Constraints:**

$1\leq$ `num.length`

$\leq 1000$ `num`

consists of digits

## Solution

We will use the greedy pattern to solve this problem. The goal is to maximize the size of the palindrome by making locally optimal choices at each step. Specifically, we aim to form the largest possible palindrome by first prioritizing using the highest digits.

The process begins by counting the frequency of each digit in the input string and storing it in a hash table. This allows us to determine how many times each digit appears. Starting with the highest digit, i.e.,

Finally, the palindrome is completed by appending the reverse of the first half to itself, with the middle digit in between, if applicable. This greedy strategy works effectively because it ensures that each decision made is the best possible choice at that moment, leading to an overall optimal solution.

Let’s review the algorithm to reach the solution:

Initialize the frequency counter

`occurrences`

to count the frequency of each digit in the input string`num`

.We also initialize the

`firstHalf`

array to note down the first part of the palindrome and the`middle`

string to track the middle element of the palindrome.Traverse digits from

$9$ to$0$ and for each digit do the following:Check if its pairs can be made by looking at its frequency. If yes, then add it to the

`firstHalf`

array.If applicable, check for the leading zeros and avoid them by explicitly setting their occurrence to

`1`

.Otherwise, check if it can be the middle element of the palindrome. Following the greedy approach, ensures that a larger number is selected to be the middle element among the elements occurring once.

Once we have processed all the elements of the

`num`

array, we join the`firstHalf`

,`middle`

, and reverse of the`firstHalf`

.Finally, we return this palindromic number, the largest that can be generated using the given number.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.