Given a string s, which may contain duplicate characters, your task is to generate and return an array of all unique permutations of the string. You can return your answer in any order.
Examples:
Input: s = "ABC" Output: ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"] Explanation: Given string ABC has 6 unique permutations.
Input: s = "ABSG" Output: ["ABGS", "ABSG", "AGBS", "AGSB", "ASBG", "ASGB", "BAGS", "BASG", "BGAS", "BGSA", "BSAG", "BSGA", "GABS", "GASB", "GBAS", "GBSA", "GSAB", "GSBA", "SABG", "SAGB", "SBAG", "SBGA", "SGAB", "SGBA"] Explanation: Given string ABSG has 24 unique permutations.
Input: s = "AAA" Output: ["AAA"]
Explanation: No other unique permutations can be formed as all the characters are same.
Constraints:
1 <= s.size() <= 9
s contains only Uppercase english alphabets
Approach 01:
-
C++
-
Python
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<string> findPermutation(string &inputString) {
vector<string> permutations; // To store all permutations of the string
string currentString = inputString; // Copy of the input string
// Sort the string to ensure permutations are generated in lexicographical order
sort(currentString.begin(), currentString.end());
// Generate all permutations using next_permutation
do {
permutations.push_back(currentString);
} while (next_permutation(currentString.begin(), currentString.end()));
return permutations;
}
};
Time Complexity:
- Sorting the string:The initial sorting of the input string takes \( O(n \log n) \), where \( n \) is the length of the input string.
- Generating permutations:Using
next_permutationgenerates all possible permutations of the string, which is \( O(n!) \). For each permutation, updating the string representation takes \( O(n) \). Therefore, generating all permutations takes \( O(n \cdot n!) \). - Overall Time Complexity:The overall time complexity is dominated by the generation of permutations and is \( O(n \cdot n!) \).
Space Complexity:
- Storage for permutations:The result vector stores all permutations, requiring \( O(n \cdot n!) \) space since there are \( n! \) permutations, and each permutation has a length of \( n \).
- Temporary string storage:A copy of the input string is maintained during the sorting and permutation process, requiring \( O(n) \) space.
- Overall Space Complexity:The overall space complexity is \( O(n \cdot n!) \).
from itertools import permutations
class Solution:
def findPermutation(self, inputString: str) -> list[str]:
# Use a set to avoid duplicate permutations, then sort them
uniquePermutations = sorted(set("".join(perm) for perm in permutations(inputString)))
return uniquePermutations
Time Complexity:
- Generating all permutations:
The
permutationsfunction from theitertoolsmodule generates all possible permutations of the input string. This operation takes \( O(n!) \), where \( n \) is the length of the input string. - Handling duplicates with a set:
Adding all \( n! \) permutations to a set requires \( O(n! \cdot n) \), as each string has a maximum length of \( n \).
- Sorting the unique permutations:
Sorting the unique permutations takes \( O(k \cdot \log k) \), where \( k \leq n! \) is the number of unique permutations. Each comparison during sorting involves comparing strings of length \( n \), so the effective time is \( O(k \cdot n \cdot \log k) \).
- Overall Time Complexity:
The overall time complexity is dominated by \( O(n! \cdot n) \), assuming \( k \approx n! \).
Space Complexity:
- Storage for permutations:
The set stores all unique permutations, requiring \( O(k \cdot n) \) space, where \( k \leq n! \) and each string has a length of \( n \).
- Temporary storage:
During generation of permutations and set operations, temporary storage of strings requires additional \( O(n) \) space.
- Overall Space Complexity:
The overall space complexity is \( O(n! \cdot n) \).