Distinct permutations of a string containing duplicates using HashSet in Java

0 0 1 minute read

Given a string str that may contain duplicate characters, the task is to print all the distinct permutations of the given string such that no permutation is repeated in the output.

Examples:

Input: str = “ABA”
Output:
ABA
AAB
BAA

Input: str = “ABC”
Output:
ABC
ACB
BAC
BCA
CBA
CAB

Approach: An approach to generate all the permutations of a given string has been discussed in this article. All the permutations generated by this approach can be stored in a HashSet in order to avoid duplicates.

Below is the implementation of the above approach:

// Java implementation of the approach 
import java.util.HashSet; 
  
public class GFG { 
  
    // To store all the generated permutations 
    public static HashSet<String> h = new HashSet<String>(); 
  
    public static void permute(char s[], int i, int n) 
    { 
  
        // If the permutation is complete 
        if (i == n) { 
  
            // If set doesn't contain 
            // the permutation already 
            if (!(h.contains(String.copyValueOf(s)))) { 
  
                h.add(String.copyValueOf(s)); 
  
                // Print the generated permutation 
                System.out.println(s); 
            } 
        } 
  
        else { 
  
            // One by one swap the jth 
            // character with the ith 
            for (int j = i; j <= n; j++) { 
  
                // Swapping a[i] and a[j]; 
                char temp = s[i]; 
                s[i] = s[j]; 
                s[j] = temp; 
  
                // Revert the swapping 
                permute(s, i + 1, n); 
  
                temp = s[i]; 
                s[i] = s[j]; 
                s[j] = temp; 
            } 
        } 
    } 
  
    // Driver code 
    public static void main(String args[]) 
    { 
        char s[] = { 'A', 'B', 'A' }; 
        permute(s, 0, s.length - 1); 
    } 
} 

Output:

ABA
AAB
BAA

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!