LeetCode 267: Palindrome Permutation II Solution

Master LeetCode problem 267 (Palindrome Permutation II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

267. Palindrome Permutation II

Medium

Hash Table String Backtracking

Problem Explanation

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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

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 your code.

What is the time complexity of LeetCode 267 (Palindrome Permutation II)?

The time complexity for LeetCode 267 (Palindrome Permutation II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 267 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 267 in Java, C++, or Python.

Back to LeetCode Solutions