Print all palindromes made from the letters of a palindrome

Updated

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()
Comment
Next tutorial
Mithlesh Upadhyay Published 18 Nov 2026 · 3 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials