How to solve LeetCode 267 (Palindrome Permutation II)?

This page provides optimized solutions for LeetCode problem 267 (Palindrome Permutation II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test and refine your code.

LeetCode 267: Palindrome Permutation II Solution

Problem Description

Explanation

To solve this problem, we need to generate all possible palindrome permutations of a given string. The approach involves counting the frequency of each character in the input string and then creating half of the palindrome string based on the even count characters. For odd count characters, we can use one character in the middle of the palindrome string. We then use backtracking to generate all permutations of the first half of the palindrome string and append the reversed string to form the final palindrome permutations.

Algorithm:

Count the frequency of each character in the input string.
Create the first half of the palindrome string based on even count characters and a middle character for the odd count character.
Use backtracking to generate all permutations of the first half of the palindrome string.
Append the reversed string to form the final palindrome permutations.

Time Complexity:

The time complexity of this algorithm is O(n * n!) where n is the length of the input string.

Space Complexity:

The space complexity of this algorithm is O(n) where n is the length of the input string.

Solutions

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

        String midChar = "";
        List<Character> oddChars = new ArrayList<>();
        StringBuilder firstHalf = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : charCount.entrySet()) {
            char c = entry.getKey();
            int count = entry.getValue();
            if (count % 2 == 1) {
                if (!midChar.isEmpty()) {
                    return result;
                }
                midChar = String.valueOf(c);
                count--;
            }
            for (int i = 0; i < count / 2; i++) {
                firstHalf.append(c);
            }
            if (count % 2 == 1) {
                oddChars.add(c);
            }
        }

        generatePermutations(firstHalf.toString().toCharArray(), 0, midChar, result);

        for (int i = 0; i < result.size(); i++) {
            StringBuilder reversed = new StringBuilder(result.get(i)).reverse();
            result.set(i, result.get(i) + midChar + reversed);
        }

        return result;
    }

    private void generatePermutations(char[] arr, int index, String midChar, List<String> result) {
        if (index == arr.length) {
            result.add(new String(arr));
        } else {
            for (int i = index; i < arr.length; i++) {
                if (!containsDuplicate(arr, index, i)) {
                    swap(arr, index, i);
                    generatePermutations(arr, index + 1, midChar, result);
                    swap(arr, index, i);
                }
            }
        }
    }

    private boolean containsDuplicate(char[] arr, int start, int end) {
        for (int i = start; i < end; i++) {
            if (arr[i] == arr[end]) {
                return true;
            }
        }
        return false;
    }

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