All Palindromic Permutations

1. You are given a string of length n.
2. You have to print all the palindromic permutations of the given string.
3. If no palindromic permutation exists for the given string, print "-1".

Note -> Check out the question video and write the recursive code as it is intended without 
               changing signature. The judge can't force you but intends you to teach a concept.

Input Format

A String of length n

Output Format

Check the sample ouput and question video.

Question Video Constraints

1 <= length of string <= 15

Sample Input

aaabb

Sample Output

ababa
baaab

• Editorial

  We can observe those cases when the palindrome will exist.

  Cases -

  Case 1 - Frequency of every character is even. (Example - "aabb", "aabbcc" for these inputs, palindrome will exist.)

  Case 2 - Number of characters with odd frequency is one and rest all the characters have even frequency. (Example - "aabbc", "a","ahbha" have palindromic permutations but "ab","aabc" does not).

  We will store the frequency of each character in a hashmap. If the number of the characters with odd frequency is more than 1, we will print -1 else we will generate all the palindromic permutations using recursion and backtracking.

  Way to generate palindromic permutation -

  We will generate the permutations for half of the frequency of each character and then append the reverse of the permutation generated.

  For example - for "aabb", frequency of each character is even therefore, it is possible to generate the palindromic permutations. We will generate the permutations for "ab" and append reverse of the permutation generated.

  Permutations for "ab" are "ab" and "ba"

  Answer - "ab" + "ba" = "abba"

   "ba" + "ab" = "baab"

  If the frequency of one of the character is odd, then we will find the permutation of characters with frequency half of the original (for odd character, frequency will be equal  to floor(freq[odd]/2)) and then append the odd character and reverse of the permutation generated.

  For example - for "aabbccc" - the permutations of "abc" are -

  "abc"

  "acb"

  "bac"

  "bca"

  "cab"

  "cba"

  Answer will be -

  "abc" +"c" + "cba" = "abccba"

  "acb" + "c" + "bca" = "acbcbca"

  "bac" + "c" + "cab" = "bacccab"

  "bca" + "c" + "acb" = "bcacacb"

  "cab" + "c" + "bac" = "cabcbac"

  "cba" + "c" + "abc" = "cbacabc"

  Signature -

  cs - current spot

  ts - total number of spots.

  fmap - HashMap that stores the half frequency of each character.

  oddc -character variable that stores the character with odd frequency(can be null)

  asf - String that stores the permutation at each level.

  Code -

  public static void main(String[] args) {
                                      Scanner scn = new Scanner(System.in);
                                      String str = scn.nextLine();
                                      HashMap
   fmap = new HashMap<>();
                                      for (int i = 0; i < str.length(); i++) {
                                  	char ch = str.charAt(i);
                                  	fmap.put(ch, fmap.getOrDefault(ch, 0) + 1);
                                      }
                                      int ofc = 0;
                                      Character oddchar = null;
                                      int length = 0;
                                      for (int i = 0; i < 26; i++) {
                                  	char ch = (char) ('a' + i);
                                  	if (fmap.containsKey(ch)) {
                                  		int freq = fmap.get(ch);
                                  		if (freq % 2 != 0) {
                                       		    oddchar = ch;
                                  		    ofc++;
                                  		}
                                  		if (ofc > 1) {
                                  		    System.out.println("-1");
                                  		    return;
                                  		}
                                  		fmap.put(ch, freq / 2);
                                  		length += (freq / 2);
                                  	}
                                      }
                                      generatepw(1, length, fmap, oddchar, "");
                                  }
                                  
                                  public static void generatepw(int cs, int ts, HashMap
   fmap, Character oddc, String asf) {
                                      if (cs == ts + 1) {
                                  	System.out.println(asf + (oddc == null ? "" : oddc) + reverse(asf));
                                  	return;
                                      }
                                  
                                      for (char ch : fmap.keySet()) {
                                  	if (fmap.get(ch) > 0) {
                                  		fmap.put(ch, fmap.get(ch) - 1);
                                  		generatepw(cs + 1, ts, fmap,oddc, asf + ch);
                                  		fmap.put(ch, fmap.get(ch) + 1);
                                  	}
                                      }
                                  }

  java false

  Code Explained -

  In the main function, we store the frequency of each character with the help of hashmap. After that we count how many characters are there with odd frequency and store the character with odd frequency in oddchar. If the characters with the odd frequency is more than 1, then we print -1 else we call the recursive function. We will also store the new len that is equal to the sum of half of frequencies of all the characters.

  Initially cs is 1, ts is equal to the new len. Fmap stores the half frequencies of each character.

  At each level we will use a FOR loop of size 26 and check whether the character is present in hashmap. If it is present, we will add it to the asf and increase the count of cs. In pre - order, we will reduce the frequency of each character by one and in post order, we will increase it by one.

  Base Case -

  When cs will be more than 1, it means we have formed permutation of all the characters. If oddc is not null, we will add it to the asf and append the reverse of the asf and print it.

  Recursion Tree -

  

  X | Y represents the characters available | answer so far.

• Asked in Companies
• Related Topics