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:
num.length
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 stringnum
.We also initialize the
firstHalf
array to note down the first part of the palindrome and themiddle
string to track the middle element of the palindrome.Traverse digits from
to 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 thefirstHalf
,middle
, and reverse of thefirstHalf
.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.