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
BAAInput: 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 ); } } |
ABA AAB BAA
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!