โ† Zoho questions

Print Distinct Permutations of String with Duplicates

Filed under Zoho

Free read 2 of 3

Sort 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

  1. Sort the string first to easily skip duplicate characters during recursion.

Solution

O(n! * n) time, O(n) space

Python
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.