Palindrome Permutation II

Problem Statement

The challenge is to generate a list of palindromic permutations derived from a given string s. A palindromic permutation is a rearrangement of the letters in the string that reads the same forward and backward. The task is to return all unique arrangements that fulfill this criteria, with no duplicate results in the list.

For cases where no palindromic permutation is possible based on the composition of s, the function must return an empty list. The answer can be presented in any sequence, implying that the order of the permutations in the output does not matter.

Examples

Example 1

Input:

s = "aabb"

Output:

["abba","baab"]

Example 2

Input:

s = "abc"

Output:

[]

Constraints

• 1 <= s.length <= 16
• s consists of only lowercase English letters.

Approach and Intuition

To tackle this problem efficiently, let's dissect the examples and constraints provided:

• Understanding Palindromes: A string is a palindrome if it reads the same backward as forward. For a permutation of the string to be a palindrome:

  • For strings of even length: Every character must appear an even number of times so it can be mirrored around a central point.
  • For strings of odd length: All characters except one must appear an even number of times. The character that appears an odd number of times will occupy the center position in the palindrome.

• Generating Permutations:

  1. Count the frequency of each character in the string.
  2. Check palindromic possibility:
     • If more than one character has an odd count in a string of even length, or more than one character has an odd count in a string of odd length, a palindromic permutation isn't possible, and we return an empty list.
  3. Form half of the palindrome:
     • For even lengths, divide the frequency of each character by two, and use these to form half of the palindrome.
     • For odd lengths, aside from the central character, divide the rest as in even lengths.
  4. Generate permutations of this half.
  5. Mirror these permutations to form full palindromes.
  6. Ensure unique permutations through use of a set or by sorting the input string.

• Complexity Considerations:

  • The length constraint (1 <= s.length <= 16) makes brute force generation of permutations feasible, as factorial growth, while exponential, is restricted by this relatively small maximum length.
  • Utilizing efficient data structures like hash maps for frequency counting and checks can streamline the process.

This methodical approach ensures that we efficiently handle generation and verification of palindromic permutations, respecting the defined conditions and constraints.

Solutions

class PalindromeGenerator {
    Set<String> resultSet = new HashSet<>();
    
    public List<String> generatePossiblePalindromes(String inputString) {
        int[] characterCount = new int[128];
        char[] halfString = new char[inputString.length() / 2];
        if (!canFormPalindrome(inputString, characterCount)) return new ArrayList<>();
        char middleChar = 0;
        int index = 0;
        for (int i = 0; i < characterCount.length; i++) {
            if (characterCount[i] % 2 == 1) middleChar = (char) i;
            for (int j = 0; j < characterCount[i] / 2; j++) {
                halfString[index++] = (char) i;
            }
        }
        permuteAndBuild(halfString, 0, middleChar);
        return new ArrayList<String>(resultSet);
    }
    
    public boolean canFormPalindrome(String str, int[] characterCount) {
        int oddCount = 0;
        for (int i = 0; i < str.length(); i++) {
            characterCount[str.charAt(i)]++;
            if (characterCount[str.charAt(i)] % 2 == 0) oddCount--;
            else oddCount++;
        }
        return oddCount <= 1;
    }
    
    void swapCharacters(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
    
    void permuteAndBuild(char[] str, int start, char middleChar) {
        if (start == str.length) {
            resultSet.add(
                new String(str) +
                (middleChar == 0 ? "" : middleChar) +
                new StringBuffer(new String(str)).reverse().toString()
            );
        } else {
            for (int i = start; i < str.length; i++) {
                if (str[start] != str[i] || start == i) {
                    swapCharacters(str, start, i);
                    permuteAndBuild(str, start + 1, middleChar);
                    swapCharacters(str, start, i);
                }
            }
        }
    }
}