Please explain me this code for tricky permutations
In this problem we need to find all the distinct permutations of string containing duplicate characters in lexicographical order.
We sorted this array for these 2 purposes
- In order to obtain the results in lexicographical ordering.
- It makes it to keep a track on the repeating characters.
For each backtracking call, we select an element and also form the remaining string. The code is similar to finding permutations with the only difference being that we are then searching if the currently selected character is the last occurence in the question string. This step is used to remove the duplicates. What we’re trying to achieve is that if there exist a character with a duplicate in the remaining string, we will ignore the present one and choose the last occurence.
For Ex: In the string AAB, we will ignore the A at 0th index as another A exists at 1st index. Both the A’s will contribute the same answers, so we can ignore either one of them (in this case we ignored the first one).
We are using the variable flag to search for the last occurence.
If the current character is last occurence, we will call for the next level, else we’ll wait for the character to reach it’s last occurence.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.