Introduction

If a string contains repeated characters, a naive permutation generator produces duplicate outputs. The clean solution is not to generate everything and deduplicate afterward, but to avoid creating repeated branches in the first place.

Why Duplicates Happen

For a string like AAB, a plain recursive permutation routine treats the two A characters as different positions. That leads to repeated paths even though swapping one A with the other does not change the final string.

The number of distinct permutations is smaller than n! when characters repeat. For example:

AAB -> AAB, ABA, BAA

So the goal is to generate each unique arrangement exactly once.

Better Than Using a Set

A set can remove duplicates after generation, but that wastes time and memory because the algorithm still explores repeated states. A better approach is to count characters and build permutations from the counts.

The idea:

1. count how many times each character appears
2. choose one available character at each recursion step
3. decrement its count
4. backtrack after exploring that branch

Because identical characters share one counter, duplicate branches never appear.

Python Example Using a Frequency Map

1from collections import Counter
2
3
4def unique_permutations(text):
5    counts = Counter(text)
6    path = []
7    result = []
8
9    def backtrack():
10        if len(path) == len(text):
11            result.append("".join(path))
12            return
13
14        for ch in sorted(counts):
15            if counts[ch] == 0:
16                continue
17
18            counts[ch] -= 1
19            path.append(ch)
20
21            backtrack()
22
23            path.pop()
24            counts[ch] += 1
25
26    backtrack()
27    return result
28
29
30print(unique_permutations("AAB"))
31print(unique_permutations("ABA"))

Output:

['AAB', 'ABA', 'BAA']
['AAB', 'ABA', 'BAA']

This works regardless of the original order because the frequency map represents character multiplicity, not position identity.

Sorted Array Plus Visited Array

Another popular solution sorts the characters and uses a visited array. At each recursion depth, if the current character equals the previous one and the previous one was not used in this branch position, skip it.

That method is correct too, but the frequency-map approach is often easier to reason about because it directly models "how many of each character remain."

Complexity

For a string of length n, the runtime is proportional to the number of unique permutations times the work to build each result. In practice, that is much better than generating all n! permutations and filtering afterward when duplicates exist.

The space cost comes from:

• the recursion depth of n
• the frequency map
• the result list if you store all permutations

If you only need to print or stream results, you can yield them one at a time instead of storing everything.

When You Only Need the Count

Sometimes you do not need the permutations themselves, only the number of unique ones. Then the answer is:

n! / (c1! * c2! * ...)

where c1, c2, and so on are the counts of repeated characters. That avoids recursion entirely.

Common Pitfalls

The biggest mistake is generating all permutations first and then using a set to clean them up. That is acceptable for tiny inputs, but it scales poorly.

Another mistake is forgetting that repeated characters must be treated as indistinguishable. Index-based recursion alone does not capture that.

A third issue is mutating shared state without undoing it during backtracking. If you decrement a count and forget to restore it, later branches will be wrong.

Summary

• Duplicate permutations arise because equal characters create repeated recursive branches.
• The best fix is to avoid duplicate branches, not to clean them up afterward.
• A frequency-map backtracking solution is simple and efficient.
• A sorted-array plus visited-array solution also works, but is a little more delicate.
• If you only need the count, use the factorial formula instead of generating permutations.