LeetCode [267] Palindrome Permutation II

LIKE CODING: LeetCode [267] Palindrome Permutation II
 Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form. 
For example: 
Given s = "aabb", return ["abba", "baab"]. 
Given s = "abc", return []. 
Hint:
If a palindromic permutation exists, we just need to generate the first half of the string.
To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.
https://discuss.leetcode.com/topic/30850/java-6ms-solution-no-reversal-or-concat
https://discuss.leetcode.com/topic/22204/my-accepted-java-solution
The idea is to start recursion from the mid position, and copy char to left and right in the char array in-place until we reach the left and right ends.
elegant!. preaclloc a buffer and use String(char[]) constructor!
one suggestion to make less parameter is : left value is enough, since right can be calculated from left.

// the idea is to build a count map for the chars in s
// and terminate if s cannot form a palindrome 
// then do DFS from the center until reaching the left/right end
// complexity: time O(n!), space O(n)
public List<String> generatePalindromes(String s) {
 List<String> result = new LinkedList<String>();
 if (s == null)
  return result;
 char[] array = s.toCharArray();
 Map<Character, Integer> map = new HashMap<Character, Integer>();
 for (int i = 0; i < array.length; i++) {
  char c = array[i];
  map.put(c, map.getOrDefault(c, 0) + 1);
 }
 Character odd = null;
 for (Map.Entry<Character, Integer> e : map.entrySet()) {
  if (e.getValue() % 2 == 1) { // odd
   if (odd != null) {
    return result;
   }
   if (array.length % 2 == 0) {
    return result;
   }
   odd = e.getKey();
  }
 }
 if (odd == null) { // s is of even length
  helper(array, result, map, array.length / 2 - 1, array.length / 2);
 } else { // odd length
  array[array.length / 2] = odd;
  map.put(odd, map.get(odd) - 1);
  helper(array, result, map, array.length / 2 - 1,
    array.length / 2 + 1);
 }
 return result;
}

private void helper(char[] array, List<String> result,
  Map<Character, Integer> map, int left, int right) {
 if (left == -1) {
  result.add(new String(array));
  return;
 }
 for (Map.Entry<Character, Integer> e : map.entrySet()) {
  if (e.getValue() >= 2) {
   e.setValue(e.getValue() - 2);
   array[left] = e.getKey();
   array[right] = e.getKey();
   helper(array, result, map, left - 1, right + 1);
   e.setValue(e.getValue() + 2);
  }
 }
}

Review https://discuss.leetcode.com/topic/22214/ac-java-solution-with-explanation

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

https://discuss.leetcode.com/topic/28020/short-backtracking-solution-in-java-3-ms
https://discuss.leetcode.com/topic/22204/my-accepted-java-solution

We only need to generate the first part of palindrome string, and the remaining part will be a middle character with the reverse of first part.

private List<String> list = new ArrayList<>();

public List<String> generatePalindromes(String s) {
    int numOdds = 0; // How many characters that have odd number of count
    int[] map = new int[256]; // Map from character to its frequency
    for (char c: s.toCharArray()) {
        map[c]++;
        numOdds = (map[c] & 1) == 1 ? numOdds+1 : numOdds-1;
    }
    if (numOdds > 1)   return list;
    
    String mid = "";
    int length = 0;
    for (int i = 0; i < 256; i++) {
        if (map[i] > 0) {
            if ((map[i] & 1) == 1) { // Char with odd count will be in the middle
                mid = "" + (char)i;
                map[i]--;
            }
            map[i] /= 2; // Cut in half since we only generate half string
            length += map[i]; // The length of half string
        }
    }
    generatePalindromesHelper(map, length, "", mid);
    return list;
}
private void generatePalindromesHelper(int[] map, int length, String s, String mid) {
    if (s.length() == length) {
        StringBuilder reverse = new StringBuilder(s).reverse(); // Second half
        list.add(s + mid + reverse);
        return;
    }
    for (int i = 0; i < 256; i++) { // backtracking just like permutation
        if (map[i] > 0) {
            map[i]--;
            generatePalindromesHelper(map, length, s + (char)i, mid);
            map[i]++;
        } 
    }
}

http://likesky3.iteye.com/blog/2238818

先按照Palindrome Permutation 的方法判断输入字符串 s 能否排列成为一个回文串。通过检查开始构造过程，有两个思路： 
思路1：按照leetcode的提示，我们仅需构造回文的前半部分。先利用前面判断过程中的map获得回文前半部分所有的字符，

相同字符排列在一起，然后按照Permutation II一题的思路获得前半部分所有的排列情况，最后组合回文的前后部分加入结果集。 
思路2：从中间往两端递归构造回文串。 

1.     // Method 1  
2.     public List<String> generatePalindromes(String s) {  
3.         List<String> ret = new ArrayList<String>();  
4.         if (s == null || s.length() == 0) return ret;  
5.         if (s.length() == 1) {ret.add(s); return ret;}  
6.         int[] map = new int[256];  
7.         for (int i = 0; i < s.length(); i++)  
8.             map[s.charAt(i)]++;  
9.         int oddCount = 0;  
10.         int oddIdx = -1;  
11.         StringBuilder half = new StringBuilder();  
12.         for (int i = 0; i < 256; i++) {  
13.             if ((map[i] & 1) == 1) {  
14.                 oddIdx = i;  
15.                 oddCount++;  
16.                 if (oddCount == 2) return ret;  
17.             }  
18.             int halfCount = map[i] / 2;  
19.             for (int j = 0; j < halfCount; j++)  
20.                 half.append((char)i);  
21.         }  
22.         List<String> halfPermutation = new ArrayList<String>();  
23.         getPermutation(half.toString().toCharArray(), new boolean[half.length()], new StringBuilder(), halfPermutation);  
24.         for (String curr : halfPermutation) {  
25.             StringBuilder curr2 = new StringBuilder(curr);  
26.             if (oddIdx != -1)  
27.                 curr += (char)oddIdx;  
28.             ret.add(curr + curr2.reverse().toString());   
29.         }  
30.         return ret;  
31.     }  
32.       
33.     public void getPermutation(char[] chars, boolean[] used, StringBuilder item, List<String> result) {  
34.         if (item.length() == chars.length) {  
35.             result.add(item.toString());  
36.         } else {  
37.             for (int i = 0; i < chars.length; i++) {  
38.                 if (used[i] || (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]))  
39.                     continue;  
40.                 item.append(chars[i]);  
41.                 used[i] = true;  
42.                 getPermutation(chars, used, item, result);  
43.                 used[i] = false;  
44.                 item.deleteCharAt(item.length() - 1);  
45.             }  
46.         }  
47.     }  
48.     // Method 2  
49.     public List<String> generatePalindromes2(String s) {  
50.         List<String> ret = new ArrayList<String>();  
51.         int[] map = new int[256];  
52.         for (int i = 0; i < s.length(); i++)  
53.             map[s.charAt(i)]++;  
54.         int oddCount = 0;  
55.         int oddIdx = -1;  
56.         for (int i = 0; i < 256; i++) {  
57.             if ((map[i] & 1) == 1) {  
58.                 oddIdx = i;  
59.                 oddCount++;  
60.                 if (oddCount == 2) return ret;  
61.             }  
62.         }  
63.         String curr = "";  
64.         if (oddIdx != -1) {  
65.             curr += (char)oddIdx;  
66.             map[oddIdx]--;  
67.         }  
68.         dfs(curr, map, s.length(), ret);  
69.         return ret;  
70.     }  
71.     public void dfs(String curr, int[] map, int n, List<String> ret) {  
72.         if (curr.length() < n) {  
73.             for (int i = 0; i < map.length; i++) {  
74.                 if (map[i] > 0) {  
75.                     curr = (char)i + curr + (char)i;  
76.                     map[i] -= 2;  
77.                     dfs(curr, map, n, ret);  
78.                     curr = curr.substring(1, curr.length() - 1);  
79.                     map[i] += 2;  
80.                 }  
81.             }  
82.         } else {  
83.             ret.add(curr);  
84.         }  
85.     }  
86. }  

https://leetcode.com/discuss/94699/java-1ms-beats-99-67%25

https://leetcode.com/discuss/53613/my-accepted-java-solution

https://leetcode.com/discuss/66099/short-backtracking-solution-in-java-3-ms

private List<String> list = new ArrayList<>(); public List<String> generatePalindromes(String s) { int numOdds = 0; // How many characters that have odd number of count int[] map = new int[256]; // Map from character to its frequency for (char c: s.toCharArray()) { map[c]++; numOdds = (map[c] & 1) == 1 ? numOdds+1 : numOdds-1; } if (numOdds > 1) return list; String mid = ""; int length = 0; for (int i = 0; i < 256; i++) { if (map[i] > 0) { if ((map[i] & 1) == 1) { // Char with odd count will be in the middle mid = "" + (char)i; map[i]--; } map[i] /= 2; // Cut in half since we only generate half string length += map[i]; // The length of half string } } generatePalindromesHelper(map, length, "", mid); return list; } private void generatePalindromesHelper(int[] map, int length, String s, String mid) { if (s.length() == length) { StringBuilder reverse = new StringBuilder(s).reverse(); // Second half list.add(s + mid + reverse); return; } for (int i = 0; i < 256; i++) { // backtracking just like permutation if (map[i] > 0) { map[i]--; generatePalindromesHelper(map, length, s + (char)i, mid); map[i]++; } } }

https://leetcode.com/discuss/72456/java-6ms-solution-no-reversal-or-concat

public List<String> generatePalindromes(String s) { List<String> result = new LinkedList<String>(); if (s == null) return result; char[] array = s.toCharArray(); Map<Character, Integer> map = new HashMap<Character, Integer>(); for (int i = 0; i < array.length; i++) { char c = array[i]; map.put(c, map.getOrDefault(c, 0) + 1); } Character odd = null; for (Map.Entry<Character, Integer> e : map.entrySet()) { if (e.getValue() % 2 == 1) { // odd if (odd != null) { return result; } if (array.length % 2 == 0) { return result; } odd = e.getKey(); } } if (odd == null) { // s is of even length helper(array, result, map, array.length / 2 - 1, array.length / 2); } else { // odd length array[array.length / 2] = odd; map.put(odd, map.get(odd) - 1); helper(array, result, map, array.length / 2 - 1, array.length / 2 + 1); } return result; } private void helper(char[] array, List<String> result, Map<Character, Integer> map, int left, int right) { if (left == -1) { result.add(new String(array)); return; } for (Map.Entry<Character, Integer> e : map.entrySet()) { if (e.getValue() >= 2) { e.setValue(e.getValue() - 2); array[left] = e.getKey(); array[right] = e.getKey(); helper(array, result, map, left - 1, right + 1); e.setValue(e.getValue() + 2); } } }

https://discuss.leetcode.com/topic/30850/java-6ms-solution-no-reversal-or-concat/2

public List<String> generatePalindromes(String s) {
 List<String> result = new LinkedList<String>();
 if (s == null)
  return result;
 char[] array = s.toCharArray();
 Map<Character, Integer> map = new HashMap<Character, Integer>();
 for (int i = 0; i < array.length; i++) {
  char c = array[i];
  map.put(c, map.getOrDefault(c, 0) + 1);
 }
 Character odd = null;
 for (Map.Entry<Character, Integer> e : map.entrySet()) {
  if (e.getValue() % 2 == 1) { // odd
   if (odd != null) {
    return result;
   }
   if (array.length % 2 == 0) {
    return result;
   }
   odd = e.getKey();
  }
 }
 if (odd == null) { // s is of even length
  helper(array, result, map, array.length / 2 - 1, array.length / 2);
 } else { // odd length
  array[array.length / 2] = odd;
  map.put(odd, map.get(odd) - 1);
  helper(array, result, map, array.length / 2 - 1,
    array.length / 2 + 1);
 }
 return result;
}

private void helper(char[] array, List<String> result,
  Map<Character, Integer> map, int left, int right) {
 if (left == -1) {
  result.add(new String(array));
  return;
 }
 for (Map.Entry<Character, Integer> e : map.entrySet()) {
  if (e.getValue() >= 2) {
   e.setValue(e.getValue() - 2);
   array[left] = e.getKey();
   array[right] = e.getKey();
   helper(array, result, map, left - 1, right + 1);
   e.setValue(e.getValue() + 2);
  }
 }

https://leetcode.com/discuss/53626/ac-java-solution-with-explanation
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); } } }

http://buttercola.blogspot.com/2015/09/leetcode-palindrome-permutation-ii.html

public class Solution {

    public List<String> generatePalindromes(String s) {

        List<String> result = new ArrayList<>();

        if (s == null || s.length() == 0) {

            return result;

        }

         

        // Step 1: determine if the string s is palindrome permutated

        Map<Character, Integer> map = new HashMap();

        if (!isPalindromePermutation(s, map)) {

            return result;

        }

         

        // Step 2: form the left half of the seed string

        StringBuffer sb = new StringBuffer();

        char middle = '\0';

         

        Iterator it = map.entrySet().iterator();

        while (it.hasNext()) {

            Map.Entry pair = (Map.Entry) it.next();

            char key = (char) pair.getKey();

            int val = (int) pair.getValue();

            while (val > 1) {

                sb.append(key);

                val -= 2;

            }

             

            if (val == 1) {

                middle = key;

            }

        }

         

        // Step 3: gnerate the permutations of the string

        permutation(sb.toString().toCharArray(), 0, result);

        List<String> result2 = new ArrayList<>();

         

        // Step 4: append the right half of the string

        for (String str : result) {

            StringBuffer tmp = new StringBuffer(str);

            if (middle != '\0') {

                tmp.append(middle);

            }

             

            for (int i = str.length() - 1; i >= 0; i--) {

                tmp.append(str.charAt(i));

            }

            result2.add(tmp.toString());

        }

         

        return result2;

    }

     

    private boolean isPalindromePermutation(String s, Map<Character, Integer> map) {

        int tolerance = 0;

        for (int i = 0; i < s.length(); i++) {

            char c = s.charAt(i);

            if (map.containsKey(c)) {

                int val = map.get(c);

                map.put(c, val + 1);

            } else {

                map.put(c, 1);

            }

        }

         

        Iterator it = map.entrySet().iterator();

        while (it.hasNext()) {

            Map.Entry pair = (Map.Entry) it.next();

            int val = (int) pair.getValue();

            if (val % 2 == 1) {

                tolerance++;

            }

        }

         

        if (tolerance <= 1) {

            return true;

        } else {

            return false;

        }

    }

     

    private void permutation(char[] s, int start, List<String> result) {

        if (start >= s.length) {

            result.add(new String(s));

            return;

        }

         

        for (int i = start; i < s.length; i++) {

            if (!containsDuplicate(s, start, i)) {

                swap(s, i, start);

                permutation(s, start + 1, result);

                swap(s, i, start);

            }

        }

    }

     

    private void swap(char[] s, int i, int j) {

        char temp = s[i];

        s[i] = s[j];

        s[j] = temp;

    }

     

    private boolean containsDuplicate(char[] s, int start, int end) {

        for (int i = start; i < end; i++) {

            if (s[i] == s[end]) {

                return true;

            }

        }

         

        return false;

    }

}


    //compute unique permutations of the first half palindrom

    void bt(string halfs, int n, int pos, vector<string> &ret, int odd_cnt, char odd_char){

        if(pos==n){

            string rev = halfs;

            reverse(rev.begin(), rev.end());

            if(odd_cnt) halfs += odd_char;

            ret.push_back(halfs+rev);

        }else{

            for(int i=pos; i<n; ++i){

                if(i>pos && halfs[i]==halfs[pos]) continue;

                swap(halfs[i], halfs[pos]);

                bt(halfs, n, pos+1, ret, odd_cnt, odd_char);

            }

        }

    }

    //compute first half of palindrome

    string getHalfS(unordered_map<char, int> &hash, char &odd_char){

        string halfs;

        for(auto h:hash){

            if(h.second%2==1){

                odd_char = h.first;

                h.second--;

            }

            for(int i=0; i<h.second/2; ++i){

                halfs += h.first;

            }

        }

        return halfs;

    }

    //compute the count of odd characters in string,

    //if it is greater than 1, there's no palindrome permutaion

    int getOddCnt(string s, unordered_map<char, int> &hash){

        int odd_cnt = 0;

        for(auto c:s){

            hash[c]++;

            if(hash[c]%2==1){

                odd_cnt++;

            }else{

                odd_cnt--;

            }

        }

        return odd_cnt;

    }

    vector<string> generatePalindromes(string s) {

        vector<string> ret;

        unordered_map<char, int> hash;

        int odd_cnt = getOddCnt(s, hash);

        if(odd_cnt>1) return ret;

        char odd_char;

        string halfs = getHalfS(hash, odd_char);

        bt(halfs, halfs.size(), 0, ret, odd_cnt, odd_char);

        return ret;

    }

http://leetcode0.blogspot.com/2016/01/267-palindrome-permutation-ii.html

    public List<String> generatePalindromes(String s) {

        Map<Character,Integer> map = new HashMap<Character,Integer>();

        for(int i =0;i<s.length();i++){

            char ch = s.charAt(i);

            map.put(ch,   map.containsKey(ch) ? map.get(ch)+1 : 1  );

        }

        return helper(map);

    }

    private List<String> helper(Map<Character,Integer> map){

        List<String> list = new LinkedList<String>();

        // declare new LinkedList to avoid ConcurrentModificationException

        for(Character ch : new LinkedList<Character>(map.keySet())){

            int count = map.get(ch);

            if(map.size()==1){// only one char, we can use

                char[] tmp = new char[count];

                Arrays.fill(tmp,ch);

                list.add(new String(tmp));

                return list;

            }

            if(count == 1) // if all odd #, will get an empy list

                continue;

            map.put(ch,count-2);

            if(count == 2)

                map.remove(ch);

            List<String> lessList = helper(map);

            for(String str : lessList)

                list.add(""+ch+str+ch);

            map.put(ch,count);

        }

        return list;

    }

1. 观察原因，应该是过多生成了新的Set（）对象？？？？？？？？？？？？？？
2. 每次都是旧的String + 新String，这样导致，要生成一个String with length n, we need  O(n^2) space and time complexity to 

网上的解法，利用了一个char[] array,  来记录每次的变化。
http://blog.csdn.net/pointbreak1/article/details/48779125
Follow up
http://www.1point3acres.com/bbs/thread-209202-1-1.html
longest palindrome string from a give string, 比如“atatdc",可以返回”atdta" /"tadat"/"atcta"/"tacat",这个题目需要返回所有可能的结果。

Read full article from LIKE CODING: LeetCode [267] Palindrome Permutation II