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
Prev Next
Permutations Words-1
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.
Approach :
Method 1- using items on levels:
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.
Method 2- using boxes on levels:
We suppose the initial level in which all the boxes are empty is the 0th level.
- In this method, we decide the first level for box 1. Box 1 has 3 choices, it can either choose to remain empty, or have item 1 in it or have item 2 in it.
- Now, for the next level for box 2, when all the boxes are empty, box2 has 3 options: to remain empty, to have item 1 in it or to have item 2 in it.
However for the second level, when one of the boxes has been previously filled by an item, then box 2 has only 2 options: to remain empty or to be filled with the item other than the one put in box1.
This has been shown by the second level of the figure. - Again, this above process is repeated for box 3 in level 3.
- The last level shows us all the possible permutations, but we only choose those as our final answer in which both the items are present (red marked permutations).
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).
- We use method 2 by taking boxes as the levels to solve this problem.
- In figure 6, the denominator part of an element represents the question/HashMap where we store the items that are left to be filled.
- The numerator part represents which items have already been filled in which boxes.
- For the string "aabb", we'll consider 4 boxes because we have 4 places to fill the items.
- For level 1, we consider box 1. Box 1 has 2 options: either to have 'a' or 'b' filled in it.
- For level 2 or box 2, we again have 2 options to fill either 'a' or 'b'.
- Reader, notice that level 3 runs similar to the previous 2 levels, except when one of the distinct items has been completely used we are left with only one option of filling the box : with the other distinct item.
- We fill the remaining one item left in the last place of box 4.
- The last level of the tree denotes all the possible permutations that are possible for the string "aabb".
HOW
Reader, the code for the above explanation is quite simple. Refer to the code given below.
import java.io.*;
import java.util.*;
public class Main {
public static void generateWords(int cs, int ts, HashMap< Character, Integer> fmap, String asf) { //cs=current spot, ts=total spots, asf= answer so far
if(cs>ts){ //1
System.out.println(asf);
return;
}
for(char ch: fmap.keySet()){ //2
if(fmap.get(ch)>0){ //3
fmap.put(ch,fmap.get(ch)-1);
generateWords(cs+1,ts,fmap,asf+ch); //4
fmap.put(ch,fmap.get(ch)+1); //5
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
HashMap< Character, Integer> fmap = new HashMap< >();
for(char ch: str.toCharArray()){
if(fmap.containsKey(ch)){
fmap.put(ch, fmap.get(ch) + 1);
} else {
fmap.put(ch, 1);
}
}
generateWords(1, str.length(), fmap, "");
}
}
java;
true";
- BASE CASE: If our current spot exceeds the total number of spots, then we return from the function.
- We run a loop in the hashmap to get unique characters.
- We check if the frequency of the character is greater than 0 i.e. it is not fully used up by the other boxes. If this condition is fulfilled, then this character is used and its frequency is decreased by 1 in the hashmap.
- Now we make a recursive call to go to the next box by increasing "cs" by one. We also add that character to the "asf" string
- While backtracking from the recursion, we again increase the frequency of the character by one.
Analysis
Time Complexity:
O(n)
Space Complexity:
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.
