**Problem Analysis:**

Suppose you have a string **P** that is already a palindrome( Empty string is also a palindrome). Now if we add a character **‘x‘** in the beginning and in the end of the string, we get **“x+P+x”**. This is also a palindrome. So by using this idea, we can get an observation that we start by creating a empty string which is a palindrome. Then we can use characters which appears even number of times. Suppose a character appears n times in the given string (if N is odd we will consider n-1 which is even). So we will add that characters n/2 times in the front and n/2 times in the back of the palindrome. Lastly if any of the occurrence of character is odd, then we can use only one from these character and use this in the middle of the palindrome. So this will still be a palindrome.

Toph uses cookies. By continuing you agree to our Cookie Policy.