Tricky Permutations

#1

Given a string with repetitive characters or an array of repetitive integers, how can we calculate unique permutations?
I went through the editorial section also but couldn’t understand the solution.
Could you please provide exhaustive explanation of this question?

#2

Hey @riyajain2372_a386c6cc4ebaf1b9 Since you are doing tricky permutation question I am assuming that you have completed Permutations with duplicates question. So here we have added some lines of code to the permutation with duplicates :

for (int j = i + 1; j < ques.length(); j++) {
                if (ques.charAt(j) == ch) {
                    flag = false;
                }
            }

            if (flag)
                permutationNoDuplicates(roq, ans + ch);

Reference(Editorial solution) : here we have taken a for loop which checks if tehr a character which is equal to ch bcoz if its equal then that character will be the reason for redundancy.So we will make flag = false; and if flag is false then current character will not be iterated by recursion and the character which made duplicacy will be recursively iterated whenever the chance comes.

#3

Hi Piyush,
Solution to Permutations with Duplicates isn’t clear either.
Along with the code, could you please explain the logic behind both of these questions?

#4

Hey @riyajain2372_a386c6cc4ebaf1b9 To explain Editorial I have added comments in the code below : (Look for the comments in between the code). If still you are unable to get the question we can do live chat from the live chat option given.

public class Main {
    public static void main(String args[]) {

        Scanner scn = new Scanner(System.in);

        String str = scn.next();

        char[] charray = str.toCharArray();
        Arrays.sort(charray);

       permutationNoDuplicates(new String(charray), "");
    }

   public static void permutationNoDuplicates(String ques, String ans) {
// base case
        if (ques.length() == 0) {
            System.out.println(ans);
            return;
        }

        for (int i = 0; i < ques.length(); i++) {
//to store current character
            char ch = ques.charAt(i);
//Getting the string excluding the current character
            String roq = ques.substring(0, i) + ques.substring(i + 1);
//Taking flag so that if there is a duplicate character in whole string after current char then we will not iterate further bcoz it will give duplicate answers.
            boolean flag = true;
//Loop to check if there is character after current character which is equal to ch and we have used this loop for the condition of flag.
            for (int j = i + 1; j < ques.length(); j++) {
                if (ques.charAt(j) == ch) {
                    flag = false;
                }
            }
//IF there is no duplicate character for ch then flag will remain true and flag = true means no duplicate char therefore cal for the remaining string.
//If there is duplicate character previous loop will make falg = false;

            if (flag)
                permutationNoDuplicates(roq, ans + ch);
//there is no else condition bcoz we don't want to do anything if duplicacy is there
        }

    }
}
#5

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.