Given a string s, generate and return all possible unique permutations of its characters in lexicographically sorted order.
Each permutation must contain all the characters of the original string.
If the string contains duplicate characters, repeated permutations should be included only once.
The final list must be sorted in ascending lexicographical order.
Example 1
Input: s = "abc"
Output: ["abc","acb","bac","bca","cab","cba"]
Explanation: Since all three characters are distinct, we can generate 3! = 6 different permutations. All six permutations are unique.
Example 2
Input: s = "aabb"
Output: ["aabb", "abab", "abba", "baab", "baba", "bbaa"]
Explanation: The characters a and b each appear twice. Although multiple swapping operations may produce the same arrangement, we include each unique permutation only once. Therefore, there are 6 unique permutations.
Brute Force Approach
A permutation can be generated by fixing one character at a time and recursively arranging the remaining characters. Start with the first position and try placing every character of the string at that position by swapping it with the current character. Once a character is placed, recursively generate all possible arrangements for the remaining positions.
When the recursive index reaches the end of the string, all positions have been filled, so the current string represents a complete permutation. Store this permutation in a set<string> to ensure that only unique arrangements are retained in lexicographical order.
After each recursive call, swap the characters back to restore the previous arrangement. This backtracking allows other characters to be placed at the current position and explores all possible arrangements.
Algorithm
An empty
setis created to store unique permutations, and the recursive function starts from index0.If the current index reaches the end of the string, the completed permutation is added to the set.
Otherwise, each character from the current index to the end is considered for the current position.
The characters are swapped to fix the current position, and the remaining positions are handled recursively.
Once the recursive call is completed, the characters are swapped back to restore the original string.
The same process continues until all possible arrangements have been generated.
Finally, the set is converted into a vector, which contains all unique permutations in lexicographical order.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to generate all permutations void solve(string &s, int index, set<string> &st) { // If the complete permutation is generated if (index == s.size()) { st.insert(s); return; } // Try swapping each character for (int i = index; i < s.size(); i++) { // Swap characters swap(s[index], s[i]); // Generate remaining permutations solve(s, index + 1, st); // Backtrack to restore the string swap(s[index], s[i]); } } // Function to return unique permutations vector<string> findPermutation(string s) { // Store unique permutations set<string> st; // Generate all permutations solve(s, 0, st); // Convert set into vector return vector<string>(st.begin(), st.end()); }};// Driver Code Startsint main() { // Example input string s = "aabb"; // Create Solution object Solution obj; // Get all unique permutations vector<string> ans = obj.findPermutation(s); // Print the result for (string str : ans) { cout << str << " "; } return 0;}Complexity Analysis
• Time Complexity: O(N × N! × log(N!)), where N is the length of the string. In the worst case, all characters are distinct, resulting in N! permutations. Each permutation is inserted into the set, taking O(N × log(N!)) time.
• Space Complexity: O(N × N!), as the set stores up to N! unique permutations, each requiring O(N) space. Additionally, O(N) space is used by the recursion stack.
Optimal Approach
The brute force approach may generate duplicate permutations when the string contains repeated characters. A better approach avoids duplicate arrangements during recursion instead of removing duplicates afterward.
At each recursive level, the current index represents the position to be filled. Every distinct character from the remaining portion of the string gets a chance to occupy the current position. A set<char> tracks the characters already considered at the current recursive level, preventing repeated choices for the same position.
After selecting a character, swapping places the selected character at the current index. Recursion then generates permutations for the remaining positions. Once the recursive call finishes, backtracking restores the previous arrangement through another swap.
When all positions are filled, a complete unique permutation is obtained and added to the answer. Skipping repeated character choices at every recursive level eliminates the need for a separate set<string> for duplicate removal.
Algorithm
Start generating permutations from the first position.
If all positions have been filled, store the current permutation in the result.
At each recursive level, maintain a set to track characters already considered for the current position.
Skip repeated characters to avoid generating duplicate permutations.
Swap each unique character into the current position and recursively generate permutations for the remaining positions.
Backtrack after each recursive call to restore the original arrangement.
Sort the generated permutations lexicographically and return the result.
Dry Run
Diagram 1
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to generate unique permutations void solve(string &s, int index, vector<string> &ans) { // If all positions are filled, store the permutation if (index == s.size()) { ans.push_back(s); return; } // Track characters already used at the current level set<char> used; // Try placing each character at the current index for (int i = index; i < s.size(); i++) { // Skip duplicate characters if (used.count(s[i])) { continue; } used.insert(s[i]); // Place the current character at the index swap(s[index], s[i]); // Generate permutations for the remaining positions solve(s, index + 1, ans); // Backtrack to restore the original string swap(s[index], s[i]); } } // Function to return all unique permutations vector<string> findPermutation(string s) { // Store the generated permutations vector<string> ans; // Start generating permutations from index 0 solve(s, 0, ans); // Sort the permutations lexicographically sort(ans.begin(), ans.end()); return ans; }};// Driver Code Startsint main() { // Example input string s = "aabb"; // Create Solution object Solution obj; // Generate unique permutations vector<string> ans = obj.findPermutation(s); // Print the result for (string str : ans) { cout << str << " "; } return 0;}Complexity Analysis
Time Complexity:
O(N × N!)in the worst case, whereNis the length of the input string. A total ofN!permutations can be generated, and each completed permutation takesO(N)time to store. Thesethelps skip duplicate characters and reduces unnecessary recursive calls.Space Complexity:
O(N × N!)for storing the generated permutations. Additionally,O(N)auxiliary space is used by the recursion stack and the set maintained at each recursive level.
Interview follow-up Questions
Backtracking restores the original arrangement of characters after each recursive call. This allows other characters to be placed at the current position and ensures that all valid unique permutations are generated.
Be the first to add a comment.