Given a string, find the lexicographically smallest palindrome if possible

Christina Preethi Nelapudi
1 min readJul 8, 2021

The idea behind this is simple, let’s divide this problem into two parts:
First we need to know whether it is possible to generate a palindrome from the given string. For this, we need to find count the frequency of each character in the string. If all the characters’ frequency is even or if there is only one character whose frequency is odd, then it is possible to generate a palindrome.

If it is possible to generate the palindrome, then from previous step, take the character that has frequency = 1(if any). Sort all the other characters in descending order and keep adding it on either side of the character that has frequency 1.

For Example:
Input : malayalam
Step 1:
frequencies of characters:
m = 2, a = 4, l = 2, y = 1
sort the characters:
['m', 'l', 'a']
Step 2:
1 --> palindrome = 'y'
2 --> palindrome = 'mym'
3 --> palindrome = 'lmyml'
4 --> palindrome = 'almymla'
5 --> palindrome = 'aalmymlaa'
Output: aalmymlaa

Find the code here: 👇👇

Hope this helped you!