A palindrome is a word, phrase or sequence that reads the same backward as forwards. Given a palindrome write a program to print the sorted list of all palindrome that can be constructed from the alphabets of the given palindrome.All palindrome should start in a new line.
Input Format:
one string(palindrome).It is confirmed that input will always be a palindrome.
Output Format:
A sorted list of all palindromes constructed from the given string. Each line should contain one palindrome.
Examples :
Input 1 : NITIN Output 1 : INTNI NITIN Explanation : There are only two strings that can be constructed from NITIN Input 2 : ABCDCBA Output 2 : ABCDCBA ACBDBCA BACDCAB BCADACB CABDBAC CBADABC Explanation : Since there is only one D, it can only be the middle letter in the palindrome. The remaining letters A, B, C can be arranged in 6 possible ways and each way gives rise to a palindrome
This problem appeared in the code Vita of this year.
Here the approach used is quite simple and efficient and it successfully passed all the test cases.
Steps to Follow:
1. First, we check whether the length of the string is even or odd.
2. if odd just store the middle letter.
3. extract the first half of the palindrome and create all the permutations of it.
4. just append the permutations with its reverse and append the middle letter if it exists.
5. finally sort the list.
Implementation :
# This method is used to create permutation of the string
def Permute(string):
if len(string) == 0:
return ['']
prevList = Permute(string[1:len(string)])
nextList = []
for i in range(0,len(prevList)):
for j in range(0,len(string)):
newString = prevList[i][0:j]+string[0]+prevList[i][j:len(string)-1]
if newString not in nextList:
nextList.append(newString)
return nextList
def App():
stringinput=input()
# just checking whether the string is of even or odd length.
odd_even= 0 if (len(stringinput) & 1)==0 else 1
# index till which there will be unique letters after that it will be repeated.
maxcheck=len(stringinput)//2-1
# if the length is odd then there will be a middle letter which will be same
# in all permutations of that string and if the string is even no such thing.
# It can be thought in this way if the length of the string is odd then there
# will be a single nonrepeated letter
if odd_even==1:
medium=stringinput[len(stringinput)//2]
else :
medium=''
liststring=[]
setstring=set()
for index,letter in enumerate(stringinput):
if index <= maxcheck:
liststring.append(letter)
liststring.sort()
inputstr=''.join(liststring)
# creating permutation of the inputstr which is string containing the sorted
# nonrepeated letters.
string = (Permute(inputstr))
output=[]
for strb in string:
reverse=strb[::-1]
# here we are just appending the string and its reverse with the middle letter
# if it exists and appends it to the list.
output.append(strb+medium+reverse)
# Lastly, we produce the sort the whole list to contain the letter in
# lexicographical order.
output.sort()
for ab in output:
print(ab)
if __name__ == "__main__":
App()