0267. Palindrome Permutation II

https://leetcode.com/problems/palindrome-permutation-ii

Description

Given a string s, return all the palindromic permutations (without duplicates) of it.

You may return the answer in any order. If s has no palindromic permutation, return an empty list.

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.

ac

class Solution {
    public List<String> generatePalindromes(String s) {
        List<String> res = new ArrayList<String>();

        // edge cases;
        if (s.length() == 0) return res;

        int[] counts = new int[128];

        // count chars
        for (char c : s.toCharArray()) {
            counts[c]++;
        }

        // determine palindrome?
        char odd = ' ';
        for (int i =  0; i < counts.length; i++) {
            if (counts[i] % 2 != 0) {
                if (odd != ' ') return res;
                odd = (char) i;
            }
        }

        // build char array for backtracking
        char[] chars = new char[s.length() / 2];
        for (int i =  0, j = 0; i < counts.length; i++) {
            while (counts[i] - 2 >= 0) {
                chars[j++] = (char) i;
                counts[i] -= 2;
            }
        }

        // backtracking
        char[] note = new char[s.length()];
        if (odd != ' ') note[s.length() / 2] = odd;
        int len = s.length() / 2;
        backtrack(chars, 0, len, note, res);

        return res;
    }

    private void backtrack(char[] chars, int k, int len, char[] note, List<String> res) {
        // exit
        if (k >= len) {
            res.add(new String(note));
            return;
        }

        // handle
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ' ') continue; // visited
            if (i > 0 && chars[i-1] != ' ' && chars[i-1] == chars[i]) continue; // duplicated

            char tmp = chars[i];
            chars[i] = ' ';
            // do sth.
            note[k] = tmp; note[note.length - 1 - k] = tmp;
            backtrack(chars, k+1, len, note, res);
            chars[i] = tmp;
        }
    }
}
/**
1. count char amount
2. determine wether palindrome
3. build an array to backtrack
4. edit array to mark visited element
5. if dulipcated, continue.
**/