Palindrome Permutation II

Updated on 20 June, 2025
Palindrome Permutation II header image

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

  • Java
java
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);
                }
            }
        }
    }
}

The Java solution provided deals with the problem of generating all possible palindromic permutations of a given string. The core of the solution involves determining if a palindrome can be formed from the string and then generating all unique permutations that constitute a palindrome.

  • Develop a method canFormPalindrome to check if any permutation of the string can be a palindrome by counting characters. A palindrome requires at most one character to have an odd number of occurrences.
  • Use an int array characterCount to keep track of the frequency of each character in the string.
  • Calculate a string halfString that contains half of each character (since the second half of the palindrome will mirror the first half).
  • Identify if there is a middle character in case of an odd-length palindrome.
  • Use the permuteAndBuild function to generate all permutations of halfString, then construct complete palindromes by appending the middle character (if any) and the reverse of the permutation.
  • Ensure uniqueness of the generated palindromes using a HashSet named resultSet.
  • Swap characters in a utility function swapCharacters to assist in generating permutations.

Follow these exact steps in the generatePossiblePalindromes method to implement the solution proficiently:

  1. Check if the input string can potentially form a palindrome. If not, return an empty list.
  2. Calculate the characterCount and prepare the halfString and identify the middle character if the string length is odd.
  3. Use recursive permutation to create palindrome strings from halfString.
  4. Convert the set of unique palindromes to a list before returning.

This approach ensures that the function efficiently generates the required list of palindrome permutations, handling edge cases like odd number of characters and avoiding duplicate palindromes effortlessly.

Comments

No comments yet.