[Recursion and Dynamic Programming] interview questions #8

[rygh4775]

Permutations with Duplicates: Write a method to compute all permutations of a string whose characters are not necessarily unique. The list of permutations should not have duplicates.

[rygh4775]

Approach

• Use hash table to create the unique permutations.

  a->2 I b->4 I c ->1

• Append remaining characters to the already pricked "prefix"

  
  P(a->2 I b->4 I c->1) = {a + P(a->1 I b->4 I C->1)} +
                      {b + P(a->2 I b->3 I C->1)} +
                      {c + P(a->2 I b->4 I c->6)}

P(a- >1 I b- >4 I C->1) = {a + P(a->6 I b- >4 I c->1)} + {b + P(a->1 I b->3 I c->1)} + {c + P(a->1 I b->4 I c- >0) } P(a- >2 I b->3 I c->1) = {a + P(a->1 I b- >3 I c->1)} + {b + P(a- >2 I b->2 I c->1)} + {c + P(a->2 I b->3 I c->6)} P(a->2 I b->4 I c ->0) = {a + P(a->1 I b- >4 I c->6)} + {b + P(a->2 I b->3 I c->6)}

### Solution
```java
ArrayList<String> printPerms(String s) {
    ArrayList<String> result = new ArrayList<>();
    HashMap<Character, Integer> map = buildFreqTable(s);
    printPerms(map, "", s.length(), result);
    return result;
}

private HashMap<Character, Integer> buildFreqTable(String s) {
    HashMap<Character, Integer> map = new HashMap<>();
    for(Character c : s.toCharArray()) {
        if(!map.containsKey(c)) {
            map.put(c, 0);
        }
        map.put(c, map.get(c) + 1);
    }
    return map;
}

private void printPerms(HashMap<Character, Integer> map, String prefix, int remaining, ArrayList<String> result) {
    if(remaining == 0) {
        result.add(prefix);
        return;
    }

    for (Character c : map.keySet()) {
        int count = map.get(c);
        if(count > 0) {
            map.put(c, count -1);
            printPerms(map, prefix + c, remaining -1, result);
            map.put(c, count);
        }
    }
}

Time complexity

• worst case O(n!), n is the length of the input string
• Best case O(n), n is the length of the input string

  Space complexity

  O(n), n is the size of hash table(the number of unique characters from the input string)

[rygh4775]

input이 abc일 경우 prefix trace

a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba