Print all Unique permutations of a given string.
Last Updated : 24 Jan, 2025
Given a string that may contain duplicates, the task is find all unique permutations of given string in any order.
Examples:
Input: "ABC"
Output: ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]
Explanation: Given string ABC has 6 unique permutations as "ABC", "ACB", "BAC", "BCA", "CAB" and "CBA".
Input: "AAA"
Output: ["AAA"]
Explanation: No other unique permutations can be formed as all the characters are same.
[Naive Approach] Generating All Permutations
The idea is to generate all possible permutations of a given string and store them in a hash set. The generated permutations were stored in hash set, to ensures that only unique permutations are retained as hashset does not allow duplicates. Once all permutations have been generated, we transfer the permutations from hash set to the result array.
This method is particularly useful when dealing with input strings that contain duplicate characters. Instead of manually handling the duplicates during the permutation generation, the use of a unordered set simplifies the process by eliminating duplicates automatically.
CPP // C++ program to print unique permutation of string using hash set. #include <algorithm> #include <iostream> #include <string> #include <unordered_set> #include <vector> using namespace std; // Function genPermutation is used to generate all possible permutaion. void genPermutation(int i, string &s, vector<bool> &used, string &curr, unordered_set<string>& st) { if (i == s.size()) { // Add the permutation to the result set st.insert(curr); return; } for (int j = 0; j < s.size(); j++) { if (!used[j]) { // Mark the character as used used[j] = true; curr.push_back(s[j]); // Recurse with the next character genPermutation(i + 1, s, used, curr,st); // Backtrack and unmark the character used[j] = false; curr.pop_back(); } } } vector<string> findPermutation(string &s) { // To track if a character is used vector<bool> used(s.size(), false); unordered_set<string> st; string curr = ""; // Start the recursion genPermutation(0, s, used, curr, st); // Convert the set to a vector vector<string> res(st.begin(), st.end()); return res; } int main() { string s = "ABC"; vector<string> res = findPermutation(s); // Print the permutations for (string perm: res) cout << perm << " "; return 0; } // Java program to print unique permutation of string using hash set. import java.util.ArrayList; import java.util.HashSet; class GfG { // Function genPermutation is used to generate all possible permutation. static void genPermutation(int i, String s, boolean[] used, StringBuilder curr, HashSet<String> st) { if (i == s.length()) { // Add the permutation to the result set st.add(curr.toString()); return; } for (int j = 0; j < s.length(); j++) { if (!used[j]) { // Mark the character as used used[j] = true; curr.append(s.charAt(j)); // Recur with the next character genPermutation(i + 1, s, used, curr, st); // Backtrack and unmark the character used[j] = false; curr.deleteCharAt(curr.length() - 1); } } } static ArrayList<String> findPermutation(String s) { // To track if a character is used boolean[] used = new boolean[s.length()]; HashSet<String> st = new HashSet<>(); StringBuilder curr = new StringBuilder(); // Start the recursion genPermutation(0, s, used, curr, st); // Convert the set to a list return new ArrayList<>(st); } public static void main(String[] args) { String s = "ABC"; ArrayList<String> res = findPermutation(s); // Print the permutations for (String perm : res) { System.out.print(perm + " "); } } } # Python program to print unique permutation of string using hash set. # Function genPermutation is used to generate all possible permutation. def genPermutation(i, s, used, curr, st): if i == len(s): # Add the permutation to the result set st.add("".join(curr)) return for j in range(len(s)): if not used[j]: # Mark the character as used used[j] = True curr.append(s[j]) # Recurse with the next character genPermutation(i + 1, s, used, curr, st) # Backtrack and unmark the character used[j] = False curr.pop() def findPermutation(s): # To track if a character is used used = [False] * len(s) st = set() curr = [] # Start the recursion genPermutation(0, s, used, curr, st) # Convert the set to a list return list(st) if __name__ == "__main__": s = "ABC" res = findPermutation(s) # Print the permutations for perm in res: print(perm, end=" ") // C# program to print unique permutation of string using hash set. using System; using System.Collections.Generic; class GfG { // Function genPermutation is used to generate all possible permutation. static void genPermutation(int i, string s, bool[] used, List<char> curr, HashSet<string> st) { if (i == s.Length) { // Add the permutation to the result set st.Add(new string(curr.ToArray())); return; } for (int j = 0; j < s.Length; j++) { if (!used[j]) { // Mark the character as used used[j] = true; curr.Add(s[j]); // Recurse with the next character genPermutation(i + 1, s, used, curr, st); // Backtrack and unmark the character used[j] = false; curr.RemoveAt(curr.Count - 1); } } } static List<string> findPermutation(string s) { // To track if a character is used bool[] used = new bool[s.Length]; HashSet<string> st = new HashSet<string>(); List<char> curr = new List<char>(); // Start the recursion genPermutation(0, s, used, curr, st); // Convert the set to a list return new List<string>(st); } static void Main(string[] args) { string s = "ABC"; List<string> res = findPermutation(s); // Print the permutations foreach (string perm in res) { Console.Write(perm + " "); } } } // JavaScript program to print unique permutation of string using hash set. // Function genPermutation is used to generate all possible permutation. function genPermutation(i, s, used, curr, st) { if (i === s.length) { // Add the permutation to the result set st.add(curr.join('')); return; } for (let j = 0; j < s.length; j++) { if (!used[j]) { // Mark the character as used used[j] = true; curr.push(s[j]); // Recurse with the next character genPermutation(i + 1, s, used, curr, st); // Backtrack and unmark the character used[j] = false; curr.pop(); } } } function findPermutation(s) { // To track if a character is used let used = Array(s.length).fill(false); let st = new Set(); let curr = []; // Start the recursion genPermutation(0, s, used, curr, st); // Convert the set to an array return Array.from(st); } // Driver Code let s = "ABC"; let res = findPermutation(s); // Print the permutations console.log(res.join(' ')); OutputCBA BAC CAB BCA ABC ACB
Time Complexity: O(n*n!), where n is the size of the array.
Auxiliary Space: O(n!), space used by hash set.
[Expected Approach] Generating Only Unique Permutations
This approach is similar to generating all possible permutation. Now in this approach, while generating the permutations, at each index during recursion, we only consider the unique available characters. To track the availability of characters we use hash map.
Duplicate permutations are generated in the previous approach because it treats identical characters, like the two 'B's in "ABBC," as distinct due to their indices. For example, when placing a 'B' at an index, choosing the first or second 'B' results in the same permutation (e.g., "ABBC" or "ABBC" again), leading to duplicates.
In this approach, we prune branches in the recursive tree that would generate duplicate permutations and place only unique available characters at each index.
C++ //C++ program to print unique permutation of string //using hash map. #include <iostream> #include <vector> #include <algorithm> #include <unordered_map> using namespace std; // Recursive function to generate permutations void genPermutations(int n, string &curr ,unordered_map<char, int> &cnt, vector<string>& res) { // Base case: If the current permutation length equals the input // string length, add it to the result if (curr.size() == n) { res.push_back(curr); return; } // Iterate through each character in the frequency map for (pair<char, int> it: cnt) { char c = it.first; int count = it.second; // Skip characters with a count of 0 if (count == 0) continue; // Include the character in the current permutation curr.push_back(c); // Decrease its count in the frequency map cnt[c]--; // Recur to build the next character in the permutation genPermutations(n, curr, cnt , res); // Backtrack: Remove the character and restore its count curr.pop_back(); cnt[c]++; } } // Function to find all unique permutations of the input string vector<string> findPermutation(string s) { // Vector to store the result vector<string> res; // Frequency map to count occurrences of each character unordered_map<char, int> cnt; // Populate the frequency map with the characters of the input string for (char c : s) cnt[c]++; // To build permutations string curr = ""; genPermutations(s.size(), curr, cnt, res); return res; } int main() { string s = "ABC"; vector<string> res = findPermutation(s); for (string perm: res) cout << perm << " "; return 0; } //Java program to print unique permutation of string //using hash map. import java.util.*; class GfG { // Recursive function to generate permutations static void genPermutations(int n, StringBuilder curr, Map<Character, Integer> cnt, List<String> res) { // Base case: If the current permutation length equals // to the input string length, add it to the result if (curr.length() == n) { res.add(curr.toString()); return; } // Iterate through each character in the frequency map for (Map.Entry<Character, Integer> entry : cnt.entrySet()) { char c = entry.getKey(); int count = entry.getValue(); // Skip characters with a count of 0 if (count == 0) continue; // Include the character in the current permutation curr.append(c); // Decrease its count in the frequency map cnt.put(c, count - 1); // Recur to build the next character in the permutation genPermutations(n, curr, cnt, res); // Backtrack: Remove the character and restore its count curr.deleteCharAt(curr.length() - 1); cnt.put(c, count); } } // Function to find all unique permutations of the input string static ArrayList<String> findPermutation(String s) { ArrayList<String> res = new ArrayList<>(); // Frequency map to count occurrences of each character Map<Character, Integer> cnt = new HashMap<>(); // Populate the frequency map with the characters of the input string for (char c : s.toCharArray()) cnt.put(c, cnt.getOrDefault(c, 0) + 1); // To build permutations StringBuilder curr = new StringBuilder(); genPermutations(s.length(), curr, cnt, res); return res; } public static void main(String[] args) { String s = "ABC"; List<String> res = findPermutation(s); for (String perm : res) System.out.print(perm + " "); } } #C++ program to print unique permutation of string #using hash map. # Recursive function to generate permutations def genPermutations(n, curr, cnt, res): # Base case: If the current permutation length equals # the input string length, add it to the result if len(curr) == n: res.append(curr) return # Iterate through each character in the frequency map for c, count in cnt.items(): # Skip characters with a count of 0 if count == 0: continue # Include the character in the current permutation cnt[c] -= 1 # Recur to build the next character in the permutation genPermutations(n, curr + c, cnt, res) # Backtrack: Restore the count cnt[c] += 1 # Function to find all unique permutations of the input string def findPermutation(s): # List to store the result res = [] # Frequency map to count occurrences of each character cnt = {} # Populate the frequency map with the characters of the input string for c in s: cnt[c] = cnt.get(c, 0) + 1 # Generate permutations genPermutations(len(s), "", cnt, res) return res if __name__ == "__main__": s = "ABC" res = findPermutation(s) print(" ".join(res)) // C# program to print unique permutation of string // using hash map. using System; using System.Collections.Generic; class GfG { // Recursive function to generate permutations static void genPermutations(int n, string curr, Dictionary<char, int> cnt, List<string> res) { // Base case: If the current permutation length equals the input // string length, add it to the result if (curr.Length == n) { res.Add(curr); return; } // Iterate through a copy of the dictionary's keys foreach (char c in new List<char>(cnt.Keys)) { int count = cnt[c]; // Skip characters with a count of 0 if (count == 0) continue; // Include the character in the current permutation curr += c; // Decrease its count in the frequency map cnt[c]--; // Recur to build the next character in the permutation genPermutations(n, curr, cnt, res); // Backtrack: Remove the character and restore its count curr = curr.Remove(curr.Length - 1); cnt[c]++; } } // Function to find all unique permutations of the input string static List<string> findPermutation(string s) { // List to store the result List<string> res = new List<string>(); // Frequency map to count occurrences of each character Dictionary<char, int> cnt = new Dictionary<char, int>(); // Populate the frequency map with the characters of the input string foreach (char c in s) { if (cnt.ContainsKey(c)) cnt[c]++; else cnt[c] = 1; } // To build permutations string curr = ""; genPermutations(s.Length, curr, cnt, res); // Convert the result list to an array return res; } static void Main(string[] args) { string s = "ABC"; List<string> res = findPermutation(s); foreach (string perm in res) Console.Write(perm + " "); } } //javascript program to print unique permutation of string //using hash map. // Recursive function to generate permutations function genPermutations(n, curr, cnt, res) { // Base case: If the current permutation length equals // the input string length, add it to the result if (curr.length === n) { res.push(curr); return; } // Iterate through each character in the frequency map for (let c in cnt) { if (cnt[c] === 0) continue; // Include the character in the current permutation cnt[c]--; // Recur to build the next character in the permutation genPermutations(n, curr + c, cnt, res); // Backtrack: Restore the count cnt[c]++; } } // Function to find all unique permutations of the input string function findPermutation(s) { // Array to store the result const res = []; // Frequency map to count occurrences of each character const cnt = {}; // Populate the frequency map with the characters of the input string for (const c of s) cnt[c] = (cnt[c] || 0) + 1; // Generate permutations genPermutations(s.length, "", cnt, res); return res; } // Driver code const s = "ABC"; const res = findPermutation(s); // Print the permutations console.log(res.join(" ")); OutputCBA CAB BCA BAC ACB ABC
Time Complexity: O(n*n!), In worst case all characters were unique, so it take time equal to generating all permutations.
Auxiliary Space: O(n), used by temporary string and hash map.
Similar Reads
DSA Tutorial - Learn Data Structures and Algorithms DSA (Data Structures and Algorithms) is the study of organizing data efficiently using data structures like arrays, stacks, and trees, paired with step-by-step procedures (or algorithms) to solve problems effectively. Data structures manage how data is stored and accessed, while algorithms focus on
7 min read
Quick Sort QuickSort is a sorting algorithm based on the Divide and Conquer that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array. It works on the principle of divide and conquer, breaking down the problem into s
12 min read
Merge Sort - Data Structure and Algorithms Tutorials Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the divide-and-conquer approach. It works by recursively dividing the input array into two halves, recursively sorting the two halves and finally merging them back together to obtain the sorted array. Merge
14 min read
Data Structures Tutorial Data structures are the fundamental building blocks of computer programming. They define how data is organized, stored, and manipulated within a program. Understanding data structures is very important for developing efficient and effective algorithms. What is Data Structure?A data structure is a st
2 min read
Bubble Sort Algorithm Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity are quite high.We sort the array using multiple passes. After the fir
8 min read
Breadth First Search or BFS for a Graph Given a undirected graph represented by an adjacency list adj, where each adj[i] represents the list of vertices connected to vertex i. Perform a Breadth First Search (BFS) traversal starting from vertex 0, visiting vertices from left to right according to the adjacency list, and return a list conta
15+ min read
Binary Search Algorithm - Iterative and Recursive Implementation Binary Search Algorithm is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N). Binary Search AlgorithmConditions to apply Binary Searc
15 min read
Insertion Sort Algorithm Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list. It is like sorting playing cards in your hands. You split the cards into two groups: the sorted cards and the unsorted cards. T
9 min read
Array Data Structure Guide In this article, we introduce array, implementation in different popular languages, its basic operations and commonly seen problems / interview questions. An array stores items (in case of C/C++ and Java Primitive Arrays) or their references (in case of Python, JS, Java Non-Primitive) at contiguous
4 min read
Sorting Algorithms A Sorting Algorithm is used to rearrange a given array or list of elements in an order. For example, a given array [10, 20, 5, 2] becomes [2, 5, 10, 20] after sorting in increasing order and becomes [20, 10, 5, 2] after sorting in decreasing order. There exist different sorting algorithms for differ
3 min read