267. Palindrome Permutation II

class Solution {
    public List<String> generatePalindromes(String s) {
        List<String> res = new ArrayList<>();
        int[] map = new int[256];
        int odd = 0;
        for (char c : s.toCharArray()) {
            map[c]++;
            
            if (map[c] % 2 == 1) {
                odd++;
            } else {
                odd--;
            }
        }
        
        if (s.length() == 0 || odd > 1) return res;
        String tmp = "";
        for (int i = 0; i < 256 && odd > 0; i++) {
            if (map[i] % 2 == 1) {
                tmp += (char) i;
                map[i]--;
                break;
            }
        }
        
        helper(res, tmp, map, s.length());
        return res;
    }
    
    private void helper(List<String> res, String tmp, int[] map, int n) {
        if (tmp.length() == n) {
            res.add(tmp);
            return;
        }
        
        for (int i = 0; i < 256; i++) {
            if (map[i] > 0) {
                map[i] -= 2;
                helper(res, (char) i + tmp + (char) i, map, n);
                map[i] += 2;
            }
        }
    }
}