PROBLEM DESCRIPTION
Given a string S. The task is to print all unique permutations of the given string that may contain dulplicates in lexicographically sorted order.
SOLUTION
BRUTE-FORCE - BACKTRACKING (ACCEPTED)
Convert string to a char array. We will try to get permutations by swapping the characters in this array. We can start with first char. Using recursion swap one by one with positions [i, n-1]. Once we are at the end of the char array, we have got one permutation. Add it to the HashSet to avoid duplicates. Convert the result to a list and return its sorted order.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public List<String> find_permutation(String s) {
// Convert the input string to a character array for easy manipulation
char[] arr = s.toCharArray();
// Use a helper function to find all permutations and store them in a set to ensure uniqueness
List<String> list = new ArrayList<String>(findPermutationHelper(arr, 0, new HashSet<>()));
// Sort the list of permutations lexicographically
Collections.sort(list);
// Return the sorted list of unique permutations
return list;
}
// Helper function to recursively find all permutations of the character array
public Set<String> findPermutationHelper(char[] s, int idx, Set<String> set) {
// Base case: if the index reaches the end of the array, add the current permutation to the set
if(idx == s.length) {
set.add(String.valueOf(s));
return set;
}
// Iterate through the array to generate all possible permutations
for(int i = idx; i < s.length; i++) {
// Swap the current element with the element at the current index
swap(s, i, idx);
// Recursively call the helper function for the next index
findPermutationHelper(s, idx + 1, set);
// Backtrack by swapping the elements back to their original positions
swap(s, i, idx);
}
// Return the set containing all unique permutations
return set;
}
public void swap(char[] arr, int i, int j) {
char t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}