Coding

Permutations of a String

Asked at

Expedia

PhonePe

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a string s, return all unique permutations of its characters in sorted order.

The output should be a list of strings, where each string is a valid permutation of s.
If the string contains duplicate characters, each permutation should appear only once.
The list should be sorted lexicographically.

You must return a list of strings, where each string is a valid permutation of s.

Input: s = "abc" Output: ["abc","acb","bac","bca","cab","cba"] **Explanation: **All 6 permutations of 3 distinct characters.

**Input: **s = "aab" Output: ["aab","aba","baa"] Explanation: Only 3 unique permutations due to duplicate 'a'.

Input: s = "aa"

1 <= s.length <= 8
s consists of lowercase English letters (a to z)
Return only unique permutations if the input string has duplicate characters

cpp

class Solution {
public:
    vector<string> permuteUnique(string s) {
        // Your code goes here
    }
};

java

class Solution {
    public List<String> permuteUnique(String s) {
        // Your code goes here
    }
}

python

class Solution:
    def permuteUnique(self, s: str) -> list:
        # Your code goes here

javascript

class Solution {
    permuteUnique(s) {
        // Your code goes here
    }
}

csharp

class Solution {
    public IList<string> PermuteUnique(string s) {
        // Your code goes here
    }
}

func permuteUnique(s string) []string {
    // Your code goes here
}

Stuck? Show a way to structure it+

01Sort the characters first.
02Track which indices are currently used.
03Build one permutation left to right.
04Skip an equal character when its previous equal copy was not used.
05Emit a copy when the path reaches the string length.

Reference answer

Sort the characters before recursing. Maintain a used array and a mutable path. At each depth, try every unused character, but when s[i] equals s[i minus one], skip i if i minus one has not been used in this branch. That rule means the first identical character must be chosen before a later identical one, so arrangements such as choosing the second a before the first are never generated. Append a character, recurse, then undo both the append and the used flag. When the path length equals n, add a copy to the result. Because candidates are considered in sorted order, emitted permutations are lexicographically sorted; no final sort is required. The number of outputs is inherently large: time is O(n times U), where U is the number of unique permutations, plus O(n log n) for sorting. Auxiliary recursion state is O(n), excluding the returned output.

Then expect these follow-ups

How would you implement this by repeatedly calling next permutation?
Tests: implementation extension
What is the output count for character frequencies c1, c2, and so on?
Tests: follow-up reasoning

Hiring now

PhonePe has 114 open roles right now

Also hiring: Expedia

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer, Backend (3-5 years)
Pune, Maharashtra, India
Software Engineer , Backend (5-7 years)
Pune, Maharashtra, India
Software Engineer, App-Android
Bengaluru, Karnataka, India

Or practice this question first

Next question