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