# 8.8. 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.

solution in 357

The easiest solution would be to create a set instead of a list.

* s = anee
* s = an, size=2
    - permutations = an, na
    - total 4
* s = ane, size=3
    - permutations = ean, ane, ena, nae + aen + nea
    - total 6, 3\*2
* s = anee, size=4
    - permutations = anee, aeen, aene
    - eaen, eane, eean, eena, enae, enea
    - naee, neae, neea
    - total 12

```python
# approach 1: building from permutations of first n-1 characters
def permutations(s):
    prm = set()
    if len(s) == 0:
        prm.append("")
        return prm
    for word in permutations(s[1:]):
        for i in range(len(word)):
            prm.add(word[:i] + s[0] + word[i:])
    return prm

print(permutations("str"))
```

## Hints

If there are many duplicate letters, it becomes inefficient to check the set each time.

> Get the count of each character, abcaac has 3a, 2c and 1b

How does that help? How can I omit doing all the permutations and checking if that permutation is already there?

> Pick a starting character. a, b, c. If you start with a, then get all permuations for 2a, 2c and 1b.

## Solution

Worst case will be O((n+1)!), but in other cases we want to only create the unique permutations.

Permutations of (a=3, b=1, c=2) is  P(2, 1, 2) + P(3, 0, 2) + P(3, 1, 1) and so on recursively for each starting character.

```python
def printPerms(string):
    result = []
    letterCountMap = defaultdict()
    for letter in string:
        letterCountMap[letter] += 1
    
    printPermsInner(letterCountMap, "", len(string), result)
    return result

def printPermsInner(letterCountMap, prefix, remaining, result):
    #base case Permutation has been completed
    if remaining == 0:
        result.append(prefix)
        return
    #try remaining letter for next char, and generate remaining permutations
    for character in letterCountMap:
        count = letterCountMap[character]
        if count > 0:
            letterCountMap[character] -= 1
            printPermsInner(letterCountMap, prefix + character, remaining - 1, result)
            letterCountMap[character] = count

print(printPerms("aaf"))
```