Print Distinct Permutations of String with Duplicates
Filed under Zoho
Free read 2 of 3Sort the string first to easily skip duplicate characters during recursion.
The question
Print all distinct permutations of a string that contains duplicate characters.
Constraints
- String length is small (e.g., <= 10).
- Output must contain no duplicates.
- Order of output does not matter.
Examples
- Input
- 'AAB'
- Output
- ['AAB', 'ABA', 'BAA']
- Why
- Duplicates are handled to ensure only unique permutations are printed.
Approach
Sort the string first to easily skip duplicate characters during recursion.
Use a boolean array to track used characters and skip adjacent identical characters if the previous one was not used.
Store valid permutations in a list and return.
Solution
O(n! * n) time, O(n) space
def get_permutations(s):
res, chars = [], sorted(list(s))
used = [False] * len(chars)
def backtrack(path):
if len(path) == len(chars): res.append(''.join(path)); return
for i in range(len(chars)):
if used[i] or (i > 0 and chars[i] == chars[i-1] and not used[i-1]): continue
used[i] = True; path.append(chars[i]); backtrack(path)
path.pop(); used[i] = False
backtrack([]); return res
Tips
- What they are testing: Test with strings containing all identical characters and strings with no duplicates.
- Common mistake: Generating all permutations first and then using a set to filter, which is inefficient.
Related Zoho questions
Collected from public candidate posts and coding forums. Updated Nov 2026.