Hello coder. We begin with the question "Permutation - words-1".
We suggest you go through the problem link, to understand the outline of the given problem.
Important Links : Problem Link, Solution Video
Hello coder. We begin with the question "Permutation - words-1".
We suggest you go through the problem link, to understand the outline of the given problem.
Important Links : Problem Link, Solution Video
You are given a word (may have one character repeat more than once) and you are required to generate and print all arrangements of these characters.
Let's first revise the concept of permutations.
If we are given n boxes and r distinct objects, then the total number of ways by which these r objects can be put into n boxes is denoted by nPr.
Hence, if we had 3 boxes and 2 distinct objects (1 and 2), then figure 2 shows all the six permutations.
You must notice that the input given by the problem, "aabb" also has 2 distinct objects (a and b).
Reader, we first see how to solve the problem for the objects (1 and 2) to be put into 3 boxes and after that relate it to the input given in the question.
Figure 3 shows us two methods of solving the given problem for 3 boxes and 2 distinct items (1 and 2). We expand on each of these methods.
In this method, we first decide item 1 as the level. For item 1, we have 3 choices, to keep it in box 1 or box 2 or box 3.
Now, for the next level we take item 2. It has only 2 choices this time because one of the three boxes has previously been filled with item 1.
The last level of the tree in Figure 4, gives us all the possible permutations.
We suppose the initial level in which all the boxes are empty is the 0th level.
We suggest you go through the solution video to understand these trees better.
Now we relate the above methods with our input string "aabb" with 2 distinct items (a and b).
Reader, the code for the above explanation is quite simple. Refer to the code given below.
java; true";
O(n)
O(1)
We are done with this question. If you face any problems in this article, we suggest you watch the solution video too.
Don't forget to check out the next question too.
For now, Goodbye.