Palindrome Permutation II

Problem Description

Given a string s, return all the possible palindromic permutations (without duplicates) of s. Return an empty list if no palindromic permutation could be formed.

Example 1:

Input: s = "aabb"
Output: ["abba","baab"]

Example 2:

Input: s = "abc"
Output: []

Naive Approach

A brute force approach would be to generate all possible permutations of the input string and then check each permutation to see if it's a palindrome. If it is a palindrome, we add it to our result set (using a Set to avoid duplicates). However, this is highly inefficient.

Code (Naive - for demonstration, not recommended)

import java.util.*;

public class Solution {
    public List<String> generatePalindromes(String s) {
        Set<String> result = new HashSet<>();
        List<String> permutations = new ArrayList<>();
        char[] chars = s.toCharArray();
        permute(chars, 0, permutations);

        for (String perm : permutations) {
            if (isPalindrome(perm)) {
                result.add(perm);
            }
        }

        return new ArrayList<>(result);
    }

    private void permute(char[] chars, int l, List<String> permutations) {
        if (l == chars.length) {
            permutations.add(new String(chars));
            return;
        }

        for (int i = l; i < chars.length; i++) {
            swap(chars, l, i);
            permute(chars, l + 1, permutations);
            swap(chars, l, i); // backtrack
        }
    }

    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }

    private boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Time Complexity (Naive)

O(n! * n), where n is the length of the string. O(n!) for generating all permutations and O(n) for checking if each permutation is a palindrome.

Space Complexity (Naive)

O(n! + n), where O(n!) is for storing all possible permutations and O(n) to store the string.

Optimal Approach

1. Character Counts: First, count the frequency of each character in the input string.
2. Odd Counts: Check the counts. A string can form a palindrome only if there is at most one character with an odd count. If there are more than one, return an empty list.
3. Build Half: Build the first half of the palindrome using half the count of each character (excluding the potential middle character with an odd count).
4. Generate Permutations: Generate unique permutations of the first half. Since we are building palindromes, the second half is just the reverse of the first half. If there's an odd-count character, put it in the middle.

Code (Optimal)

import java.util.*;

public class Solution {
    public List<String> generatePalindromes(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char c : s.toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }

        int oddCount = 0;
        Character oddChar = null;
        for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
            if (entry.getValue() % 2 != 0) {
                oddCount++;
                oddChar = entry.getKey();
            }
        }

        if (oddCount > 1) {
            return new ArrayList<>(); // No palindrome possible
        }

        String half = buildHalf(counts);
        List<String> result = new ArrayList<>();
        permuteUnique(half.toCharArray(), 0, result, oddChar);

        return result;
    }

    private String buildHalf(Map<Character, Integer> counts) {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
            char c = entry.getKey();
            int count = entry.getValue() / 2;
            for (int i = 0; i < count; i++) {
                sb.append(c);
            }
        }
        return sb.toString();
    }

    private void permuteUnique(char[] chars, int l, List<String> result, Character oddChar) {
        if (l == chars.length) {
            String half = new String(chars);
            String palindrome = half + (oddChar == null ? "" : oddChar) + new StringBuilder(half).reverse().toString();
            result.add(palindrome);
            return;
        }

        Set<Character> seen = new HashSet<>();
        for (int i = l; i < chars.length; i++) {
            if (seen.add(chars[i])) {
                swap(chars, l, i);
                permuteUnique(chars, l + 1, result, oddChar);
                swap(chars, l, i); // backtrack
            }
        }
    }

    private void swap(char[] chars, int i, int j) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}

Time Complexity (Optimal)

O((n/2)! * n), where n is the length of the string. Building the half string takes O(n). Generating unique permutations of the half string which has a length of approximately n/2 takes O((n/2)!). Each permutation requires O(n) to create the full palindrome string.

Space Complexity (Optimal)

O(n), where n is the length of the string. O(n) space for storing character counts and other strings.

Edge Cases

• Empty string: Should return a list containing only an empty string.
• String with only one character: Should return a list containing the string.
• String with no possible palindrome: Should return an empty list.
• String with repeated characters, like 'aaaa': Should return [aaaa]