Palindrome Permutation of a String in Java

A string inStr is provided to us. Our task is to find and print all the palindromes that is possible from the string inStr. Note that all of the characters of the string inStr have to be used to generate the palindromes. If a palindrome does not exist, then display an appropriate message.

Given a string, we need to print all possible palindromes that can be generated using letters of that string. Examples:

Example 1:

Input

String inStr = "ttpkkp"

Output

"ptkktp", "pkttkp", "tpkkpt", "tkppkt", "kpttpk", "ktpptk" are the palindromic permutation of the input string.

Explanation:

These are the only strings that have included all of the characters of the input string inStr and are also palindrome.

Example 2:

Input

String inStr = "kkbbckdkd"

Output

"kkbdcdbkk" "kkdbcbdkk" "kbkdcdkbk" "kbdkckdbk" "kdkbcbkdk" "kdbkckbdk" "bkkdcdkkb" "bkdkckdkb" "bdkkckkdb" "dkkbcbkkd" "dkbkckbkd" "dbkkckkbd"

Explanation:

These are the only strings that have included all of the characters of the input string inStr and are also palindrome.

Example 3:

Input

String inStr = "kkb"

Output

"kbk"

Explanation:

The only string "kbk" includes all of the characters of the input string inStr and is also a palindrome.

Simple Approach

The simple approach is to find out all the subsets of the string inStr. After that, filter out those subsets whose size is equal to the inStr. In the filtered-out subsets, check those subsets that are palindrome and print them.

FileName: PalindromePermutation.java

Output:

For the string: ttpkkp The permutated palindrome strings are: kpttpk tpkkpt ktpptk ptkktp pkttkp tkppkt For the string: kkbbckdkd The permutated palindrome strings are: kbdkckdbk bdkkckkdb kkbdcdbkk kdkbcbkdk dkkbcbkkd kdbkckbdk bkkdcdkkb kbkdcdkbk dbkkckkbd kkdbcbdkk dkbkckbkd bkdkckdkb For the string: kkb The permutated palindrome string is: kbk 

Complexity Analysis: The program is doing the permutation of the string. The program is also using loops. However, the permutation of the string is the main time-consuming process, which makes the time complexity of the program O(n!). Also, the program is using hash set to store the permutation of the input string. Thus, the space complexity of the program is also O(n! x n), where n is the total number of characters present in the input string.

After looking at the complexity analysis of the above program, it is obvious that some optimization is required. It is because the complexity of the above program is large. Before writing the program, let's see the following steps.

Step 1: First, it is required to check whether using the characters of the input string can generate a palindrome or not. If it is not possible to generate a palindrome, then return.

Step 2: After doing the checking in the first step, we can create the half part of the first palindrome string (lexicographically smallest) by considering the half frequency of each character of the input string.

Step 3: Now iterate through all of the permutations that are possible of the half string, and every time adds the reverse of this part at the end.

Step 4: Add the character having an odd frequency in between if the string is of the odd length for making the palindrome.

Now, observe the following program.

FileName: PalindromePermutation1.java

Output:

For the string: ttpkkp The permutated palindrome strings are: ktpptk ptkktp pkttkp tkppkt kpttpk tpkkpt For the string: kkbbckdkd The permutated palindrome strings are: dbkkckkbd kdbkckbdk kkbdcdbkk dkkbcbkkd kdkbcbkdk kbkdcdkbk bdkkckkdb bkkdcdkkb kbdkckdbk kkdbcbdkk bkdkckdkb dkbkckbkd For the string: kkb The permutated palindrome string is: kbk 

Complexity Analysis: The program is doing the permutation of half of the string. That makes the time complexity of the program O((n / 2)!). Also, the program is using hash set to store the permutation of the input string. Thus, the space complexity of the program is also O((n / 2)! x n / 2), where n is the total number of characters present in the input string.