HackerEarth - Shil, and Palindrome Solution
1 min read

HackerEarth - Shil, and Palindrome Solution

HackerEarth - Shil, and Palindrome Solution

Shil is your new boss and he likes palindromes very much. Palindrome is a string that can be read the same way in either direction, from the left to the right and from the right to the left. (ex. madam , aabaa, racecar)

Given a string S , beautiful Palindrome is a lexicographical minimum palindrome that can be formed by rearranging all the characters of string S. In order to please your boss, find a beautiful Palindrome that can be formed with help of string S.

String x is lexicographically less than string y, if either x is a prefix of y (and x ≠ y), or there exists such i (1 ≤ i ≤ min(|x|, |y|)), that xi < yi, and for any j (1 ≤ j < i) xj = yj. Here |a| denotes the length of the string a. The lexicographic comparison of strings is implemented by operator < in modern programming languages​​.

Input:
Only line of input contains string S. All the letters of this string will be in lower letters('a' - 'z').

Output:
Output lexicographical minimum Palindrome that can be formed by rearranging all the letters of string S. If no such Palindrome exist for given input, print -1.

Constraints:
1≤|S|≤100000

SAMPLE INPUT

aabcc 

SAMPLE OUTPUT

acbca 

Explanation

After rearranging all the characters , all the palindromes that can be formed are cabac and acbca. Out of these two lexicographical minimum one is acbca.

Solution in Python

import sys
from collections import Counter
s = input().strip()
c = Counter(s)
pal = ""
mid = ""
odd = 0

for k,v in c.items():
    if v%2:
        odd+=1
        mid+=k
        v-=1
    pal+=k*(v//2)

if odd > 1 :
    print("-1")
else:
    pal = "".join(sorted(pal))
    print(pal+mid+pal[::-1])

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×