Java 2 ms, using a linked list to avoid unnecessary looping


  • 0

    My first solution was a typical hashmap/backtracking 7 ms one. However, I didn't particularly like the part when it checks whether there are any instances of a character left. That's the part that looks something like this:

            int count = e.getValue();
            if (count == 0) {
                continue;
            }
    

    When we get closer and closer to the middle, these line hit more and more often, so we end up running almost the entire loop in vain. So I thought that it would be nice to remove the character from the list for good when the count reaches zero. But if we do that with a hashtable, the iterations will start throwing ConcurrentModificationException. So we need to store characters with counts in a structure that supports instant removals and re-insertions (for backtracking). That's obviously a linked list. We can't use LinkedList, though because of the same reason—concurrent modifications aren't allowed. So I had to roll out my simple singly-linked list implementation.

    This only improved 7 ms to 6 ms. That's not a big surprise, though, since it's still the same order complexity. I got 2 ms by doing away with the hashmap.

    On a side note, I see a lot of solutions using int[128] or int[256] for the frequency table. This will obviously screw up anything containing non-ASCII characters and the problem does not say it's limited to Latin characters. One interesting question to ask if you encounter this problem at an interview is are characters limited to ASCII or even BMP. Because if there are characters outside BMP, we may have to handle surrogate pairs, so even int[65536] / HashMap<Character, Int> solutions are, strictly speaking, incorrect!

    public List<String> generatePalindromes(String s) {
        int[] freq = new int[65536];
        char[] chars = new char[s.length()];
        int ch = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (++freq[c] == 1) {
                chars[ch++] = c; // save distinct characters
            }
        }
        List<String> result = new ArrayList<>();
        boolean odd = false;
        char[] buffer = new char[s.length()];
        Node head = null, tail = null;
        for (int i = 0; i < ch; ++i) {
            char c = chars[i];
            int count = freq[c];
            if (count % 2 != 0) {
                if (s.length() % 2 == 0 || odd) {
                    return result;
                } else {
                    odd = true;
                    buffer[buffer.length / 2] = c;
                }
                if (--count == 0) {
                    continue;
                }
            }
            Node n = new Node(c, count / 2);
            if (head == null) {
                head = tail = n;
            } else {
                tail.next = n;
                tail = n;
            }
        }
        buildCombinations(result, head, buffer, 0);
        return result;
    }
    
    private static void buildCombinations(List<String> result, Node head, char[] buffer, int pos) {
        if (pos == (buffer.length | 1) / 2) {
            result.add(new String(buffer));
            return;
        }
        Node current = head, prev = head;
        while (current != null) {
            buffer[pos] = buffer[buffer.length - 1 - pos] = current.c;
            if (current.count == 1) {
                if (current == head) {
                    buildCombinations(result, head.next, buffer, pos + 1);
                } else {
                    prev.next = current.next;
                    buildCombinations(result, head, buffer, pos + 1);
                    prev.next = current; // backtrack
                }
            } else {
                --current.count;
                buildCombinations(result, head, buffer, pos + 1);
                ++current.count; // backtrack
            }
            prev = current;
            current = current.next;
        }
    }
    
    private static class Node {
        final char c;
        int count;
        Node next;
        
        Node(char c, int count) {
            this.c = c;
            this.count = count;
        }
    }

Log in to reply
 

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