Permutations of a String

19
0

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 set is created to store unique permutations, and the recursive function starts from index 0.

  • 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
1 / 3

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 Starts
int 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
1 / 2

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 Starts
int 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, where N is the length of the input string. A total of N! permutations can be generated, and each completed permutation takes O(N) time to store. The set helps 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.

RecursionString

Read Similar Blogs

Comments0