Tricky permutation (can't figure out the solution)

#1

I can’t figure out the logic for this…pls can someone help me in understanding and solving this problem

#2

@10vaibhavsinghnegi,

Write a recursive function that will generate all the permutations of the string.

Terminating condition will be when the passed string is empty, in that case the function will return an empty ArrayList.

Before adding the generated string, just check if it has already been generated before to get the distinct permutations.

If you can generate the substrings of strings containing only distinct characters, then in this question, only modification will be to check whether the same substring has been generated before or not.

#3

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.

#4

import java.util.*;
public class Main {
static ArrayList res = new ArrayList();

// display
public static void display(ArrayList<String> arr) {
	for (String string : arr) {
		System.out.println(string);
	}
}

public static void sort() {
	for (int i = 0; i < res.size(); i++) {
		for (int j = i + 1; j < res.size(); j++) {
			if (res.get(i).compareTo(res.get(j)) > 0) {
				String temp = res.get(i);
				res.set(i, res.get(j));
				res.set(j, temp);
			}
		}
	}
}

public static void trickeyPermutation(String str, String ans) {

	if (str.length() == 0) {
		if (!res.contains(ans)) {
			res.add(ans);
		}
		return;
	}

	for (int i = 0; i < str.length(); i++) {
		char cc = str.charAt(i);
		String ros = str.substring(0, i) + str.substring(i + 1);
		trickeyPermutation(ros, ans + cc);
	}
}

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	String str = sc.nextLine();
	trickeyPermutation(str, "");
	sort();
	display(res);
}

}

#5

i am getting TLE in test case 0 but rest all are passing…pls help me with this

#6

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.

#7

hi @10vaibhavsinghnegi
Your code will give TLE for ABCDEFGH or any input whose length is greater than 7. Try to optimize it.

#8

can you give any suggestions how can i optimize it further?

#9

@saurabh_singhCmn your sort function is taking time so try to reduce its complexity.

#10

I tried but was not able to reduce its complexity can you help me with this?