Full lesson preview

Generate all permutations of a string

Return all unique permutations of the characters in a string, sorted lexicographically.

Python practice8 minRecursion & BacktrackingBeginnerLast updated March 27, 2026

Problem statement

Given a string s, generate all unique permutations of its characters and return them as a list of strings sorted in lexicographic order. Handle duplicate characters by ensuring each distinct permutation appears only once. The function should return a list (possibly containing the empty string if s is empty).

Task

Practice recursion and handling duplicates by generating all unique permutations of a string.

Examples

Basic example

Input

'ab'

Output

['ab', 'ba']

Two characters have two permutations: 'ab' and 'ba'.

With duplicates

Input

'aba'

Output

['aab', 'aba', 'baa']

Although there are 3! = 6 arrangements, duplicates collapse to 3 unique permutations sorted lexicographically.

Input format

A single string s.

Output format

A list of unique permutation strings sorted lexicographically.

Constraints

0 <= len(s) <= 8 (to keep output reasonable); characters can repeat.

Samples

Sample 1

Input

'abc'

Output

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

All permutations of a 3-character string.