AC Java solution with explanation


  • 55

    Basically, the idea is to perform permutation on half of the palindromic string and then form the full palindromic result.

    public List<String> generatePalindromes(String s) {
        int odd = 0;
        String mid = "";
        List<String> res = new ArrayList<>();
        List<Character> list = new ArrayList<>();
        Map<Character, Integer> map = new HashMap<>();
    
        // step 1. build character count map and count odds
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
            odd += map.get(c) % 2 != 0 ? 1 : -1;
        }
    
        // cannot form any palindromic string
        if (odd > 1) return res;
    
        // step 2. add half count of each character to list
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            char key = entry.getKey();
            int val = entry.getValue();
    
            if (val % 2 != 0) mid += key;
    
            for (int i = 0; i < val / 2; i++) list.add(key);
        }
    
        // step 3. generate all the permutations
        getPerm(list, mid, new boolean[list.size()], new StringBuilder(), res);
    
        return res;
    }
    
    // generate all unique permutation from list
    void getPerm(List<Character> list, String mid, boolean[] used, StringBuilder sb, List<String> res) {
        if (sb.length() == list.size()) {
            // form the palindromic string
            res.add(sb.toString() + mid + sb.reverse().toString());
            sb.reverse();
            return;
        }
    
        for (int i = 0; i < list.size(); i++) {
            // avoid duplication
            if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) continue;
    
            if (!used[i]) {
                used[i] = true; sb.append(list.get(i));
                // recursion
                getPerm(list, mid, used, sb, res);
                // backtracking
                used[i] = false; sb.deleteCharAt(sb.length() - 1);
            }
        }
    }

  • 0

    Nice and straightforward. Thanks a lot!


  • 0
    Z

    Good idea to carry around half of the string, and populate the other half when necessary.


  • 1
    D

    Why do you need to call "sb.reverse()" once you find a solution?


  • 0
    K

    sb is reversed first time here: res.add(sb.toString() + mid + sb.reverse().toString());
    To restore the original sequence, you have to reverse back


  • 1

    Hi @jeantimex, I have a little confusion about the duplicates avoidance, how do you use used[] to avoid duplicates. Could you please explain the following line?

    if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) continue;
    

    Thank you!


  • 0

    @jeantimex, please ignore the previous comment I left, I have understood it, that is really awesome! I used to use a hash set to avoid duplicates when the whole string built, but with the used[], we can avoid it in the at a very early time. Thank you for your solution.


  • 2
    Z

    I got a quick question. For the permutation II, we need to sort the array in order to avoid the duplicates. And for you solution, you did not sort the list. Can anyone tell me why it is still working?


  • 5
    A

    @zws1818918 In permutation II, we sort the list because we just want to make sure that same elements can be located at adjacent positions, and here when we iterate the map, we already put the same elements together. Therefore, we don't need to sort the list here since the general order doesn't matter.


  • 0
    G

    @zws1818918 Because when we add the key into the list in step 2, we add the keys from the same entry until there's no more key in the same entry. So the keys added in list already has the duplicate keys together. Thus we don't need to sort the list again later.


  • 0
    B

    Can some1 explain to me how mid works. e.g 'bacb'


  • 0

    @jeantimex I'm not pretty sure if mine is correct. Thanks in advance if you or someone else could do me a favor to confirm.

        public List<String> generatePalindromes(String str) {
            int[] dict = new int[256];
            for (char c : str.toCharArray())
                dict[c]++;
    
            List<String> ret = new ArrayList<>();
            String odd = null;
            for (int i = 0; i < dict.length; i++) { // If there is single char, then it must be in middle
                if (dict[i] == 1) {
                    if (odd == null) odd = String.valueOf((char) i);
                    else return ret;
                }
            }
            generate(ret, (odd == null) ? "" : odd, dict, str.length());
            return ret;
        }
    
        private void generate(List<String> ret, String path, int[] dict, int max) {
            if (path.length() == max) {
                ret.add(path);
                return;
            }
    
            for (int i = 0; i < dict.length; i++) {
                if (dict[i] >= 2) { // Only use once for same character
                    dict[i] -= 2;
                    generate(ret, (char) i + path + (char) i, dict, max);
                    dict[i] += 2;
                }
            }
        }
    

    I just tried to follow the common template for combinatrial problem to traverse the tree of search space.

    0_1482856675749_IMG_3202.jpeg


  • 0
    M

    I think time complexity is, O(n^n), n=s.length()/2


  • 2

    I believe this is much Simpler Implementation.

       public List<String> generatePalindromes(String s) {
            List<String> ans = new ArrayList<>();
            int [] count = new int [256]; int odds = 0;
            for (char c : s.toCharArray()) count [c] ++;
            for (int c : count) if (c % 2 != 0) odds ++;
            if (odds <= 1) {
                Character center = null;
                for (int idx = 0; idx < count.length; idx ++) 
                    if (count [idx] % 2 == 1) { 
                        center = ((char) idx); 
                        count [idx] --; 
                        break; 
                    }
                        
                generate (ans, count, (center != null ? String.valueOf(center) : new String ()), s.length());
            }
            return ans; 
        }
        
        private void generate (List<String> ans, int[] count, String build, int len) {
            for (int idx = 0; idx < count.length; idx ++) {
                if (count [idx] > 0) {
                    count [idx] -= 2;
                    generate (ans, count, ((char) idx) + build + ((char) idx), len);
                    count [idx] += 2;
                }
            }
            if (build.length() == len) ans.add (new String (build));
        }
    

  • 0
    M

    I have the similar idea, but I have problem is what the time complexity of it?

    public class Solution {
        public List<String> generatePalindromes(String s) {
            List<String> res = new ArrayList<String>();
            // corner case
            if (s == null && s.length() == 0) {
                res.add("");
                return res;
            }
            // use hashMap
            HashMap<Character, Integer> map = new HashMap<>();
            char[] c = s.toCharArray();
            for (char i : c) {
                if (!map.containsKey(i)) map.put(i, 1);
                else map.put(i, map.get(i) + 1);
            }
            // determine
            int count = 0;
            boolean isV = true;
            char oddc = 'a';
            for (char cc: map.keySet()) {
                if (map.get(cc) % 2 == 1) {
                    oddc = cc;
                    count++;
                }
                if (count > 1) isV = false;
            }
            if (!isV) return res;
            // now the num can be P
            List<Character> list = new ArrayList<>(map.keySet());
            if (s.length() % 2 == 1) {
                map.put(oddc, map.get(oddc) - 1); 
                if (map.get(oddc) == 0) map.remove(oddc);
                dfs(res, "" + oddc, map, s.length(), list);
            } else {
                dfs(res, "", map, s.length(), list);
            }
            return res;
        }
        private void dfs(List<String> res, String s, HashMap<Character, Integer> map, int len, List<Character> mem) {
            if (s.length() == len) {
                if (!res.contains(s)) res.add(s);
                return;
            }
            for (char c: mem) {
                if (!map.containsKey(c)) continue;
                map.put(c,map.get(c) - 2);
                if(map.get(c) == 0) map.remove(c);
                dfs(res, c + s + c, map, len, mem);
                map.put(c, map.getOrDefault(c, 0) + 2);
            }
        }
    }
    

  • 1

    I really like the way you deal with duplicates: if there are duplicates, use the first one of unused or skip it.


  • 0
    Y
    This post is deleted!

  • 0
    H

    To who are confused with the way @jeantimex deal with duplicates,

    if (i > 0 && list.get(i) == list.get(i - 1) && !used[i - 1]) continue;
    

    here is a simple explanation: think about the following string baaaccd,

                skip the following 3 characters
                   |  |     |
            [b, a, a, a, c, c, d]
    

    When we have tried the permutation begin with ba, we don't want to try another ba, so just skip the following 2 a, and build the permutation from bc.

    The same thing happens when we meet the 2nd c.


  • 0
    H

    Another hint, although the Backtracking works well for this problem. We can also use Dynamic Programming to solve Permutation.

        /* Dynamic Programming */
        private Set<String> permutation(String letters) {
            Set<String> result = new HashSet<>();
            if (letters.length() == 0) { return result; }
            if (letters.length() == 1) { result.add(letters); return result ; }
            char c = letters.charAt(0);
            Set<String> subSet = permutation(letters.substring(1));
            for (String str : subSet) {
                int len = str.length();
                for (int i = 0; i <= len; i++) {
                    result.add(str.substring(0,i) + c + str.substring(i,len));
                }
            }
            return result;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.