The most important property of a program is whether it accomplishes the intention of its user.
Words-K Length Words-2
Welcome back, dear reader. In this article we will discuss this problem called WORDS-K LENGTH WORDS-2. So, what does this question say? Have a look at the image given below:
We will be given an input string and an integer representing the size of the words. We are required to print all the words of length k where k is the input integer with no repeating character. For instance, in the above example the input string was "abcabc" and we had to generate all the words of length 2. There were 6 possible words that we generated without the repetition of any character. Also note that the string which is received as an input can contain duplicate characters but we do not want to include any duplicate characters in our words. Also, you cannot have duplicate words either. What do we mean by this?
See, in the above example, we had 'a', 'b' and 'c' each two times. So, you might think that we can make the word "ab" two times, once using the first 'a' and 'b' and the other time using the other two. So, you can't do this. Neither the words nor the characters in the words should be duplicated.
We recommend you refer to the K LENGTH WORDS-1 to understand the question completely. We recommend you try to solve this problem yourself first and then refer to the solution. We hope that you have solved this problem K LENGTH WORDS-1 as this is the same problem and we have discussed one approach in this. In this article, you will see the opposite of the previous approach.
Approach :
Time Complexity: O(n x m) where n is the length of the string and m is the length of the words that we have to make.
Space Complexity: O(m) considering the recursion space.
Explanation:
Do you remember the question that we solved previously. Let us remind you of that question. Have a look at the image shown below:
We have 3 boxes and we have 2 distinct items, we have to write all the ways of arranging the items into these boxes. The ways of arranging 2 distinct items in three boxes is shown above. Now, compare it with our question. We are given the input string as "abcabc" (just an example, the string can be any string that user inputs). Now, this is just to confuse us.
If we look at the string carefully, we will understand that we have only 3 distinct characters and they are 'a', 'b' and 'c'. If we are said that we have to create all the words of length 2, we have actually the same situation as above.
You can see that we can visualize our question into the items and boxes as shown in the figure above. So, when we discussed the first approach in the K LENGTH WORDS-1, we kept the boxes at the levels and corresponding to the boxes, we kept the characters at the levels.
So, we have already had a great discussion on the fact that the boxes correspond to the characters of the string in this problem and not the spots (although it appears to be the opposite). If you have any questions or doubts regarding this that how the boxes correspond to the characters, we recommend you go through the K LENGTH WORDS ARTICLE once where we have discussed all of this in detail.
Now, let us take the opposite procedure. Let us now keep the items at the levels and the boxes will be the options. Remember that now, there will be no call which corresponds to option "no". What do we mean by this?
Well, when we had boxes at the levels, we had an option that there will not be any item in the box as the number of boxes is greater than the number of items. But, when we have placed the items on the levels, we do not have a "no" call in recursion as the items have to be placed in one of the boxes as they are less than the boxes. So, let us start with the same discussion.
We have 2 unique items (1 and 2) and three boxes. So, we have item 1 at the first level in the recursion tree. It has three choices i.e. to go to box 1 or 2 or 3 but it has to go to one of the boxes. There is no option for the item to not be kept in any of the boxes as the items are less than the number of boxes:
Now, at the next level, we will have the item 2. Since we have already kept the item 1 at one box, we will now have only two options for the item 2.
This is how we will fill the boxes with 2 unique items. We hope that you have understood this procedure. We suggest that you watch the solution video to understand the above explained procedure completely.
Now, let us try to apply this procedure to our question as well and see how we can apply the same procedure for our question.
We have already discussed that the boxes correspond to the characters and the items to the spots. Let us implement the same here.
Let us say that we have the input string "abcabc". So, the unique characters in this string are 'a', 'b' and 'c'. Now, let us say that we have to make words of length 2. So, we have 2 spots to fill. Let's start with the procedure.
So, we have two spots here now. The first spot is at level 1. So, we have three options to fill here i.e. 'a' or 'b' or 'c'.
After this, at the next level, we have the spot 2. Now, we have already occupied the spot 1 with one of the tree characters. So, the spot 2 has only two choices left.
So, we have now obtained all the words of length 2 that can be formed from the string "abcabc". We hope that you have understood the procedure. If you have any doubts regarding it, refer to the solution video to understand the above procedure and the concept of dissimilarity of the box and the spots.
Now, let us do a quick overview of what we have to do in the code.
What we have to do in the code?
We will take a hashset. We will read the input string character by character and put each character into the hashset if it is not already present in the hash set and simultaneously, we will add these characters into the unique string. If a character is already present in the hashset, it will not be added to it and the string. This will help us get a string which contains only unique characters.
We will have a hashset called used which will tell us about the characters that we have already use to occupy a particular spot.
Also, we are using backtracking and you know what you have to do when you return from the recursion. Take this as a hint and try to write the code on your own now.
Now that we know the entire procedure and have an idea about what we have to do in the code too, let us now write the code.
import java.io.*;
import java.util.*;
public class Main {
public static void generateWords(int cs, int ts, String ustr, HashSet< Character> used, String asf) {
if (cs > ts) {
System.out.println(asf);
return;
}
for(int i = 0; i < ustr.length(); i++){
char ch = ustr.charAt(i);
if(used.contains(ch) == false){
used.add(ch);
generateWords(cs + 1, ts, ustr, used, asf + ustr.charAt(i));
used.remove(ch);
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int k = Integer.parseInt(br.readLine());
HashSet< Character> unique = new HashSet< >();
String ustr = "";
for (char ch : str.toCharArray()) {
if (unique.contains(ch) == false) {
unique.add(ch);
ustr += ch;
}
}
generateWords(1, k, ustr, new HashSet< >(), "");
}
}
java;
true";
So, dear reader, we hope that you have understood the code completely. If you have any doubts about it, refer to the solution video to understand the above code completely. Now let us discuss the rtime and space complexity.
Analysis
Time Complexity:
The time complexity of this solution is O(n x m) where n is the number of unique characters in the string and m is the length of words that we have to make. This is because there are m levels in the tree and at every level, the maximum choices that we have is n.
Best Case: If the input string has all the characters same then the number of unique characters is 1. Also, in such a case, we can not make a word of more then 1 length (why??). So, m is also 1. Therefore the time complexity becomes O(n x m)=O(1).
Worst Case: The worst case is when the entire string has no duplicate character. So, in this case is we have to make a word of length m and the string has a length n which is also the number of unique characters in this case then the time complexity will be O(n x m).
Average Case: The average case is same as the worst case. So, the time complexity is O(n x m). Here, n is the number of unique characters to be precise but since it is taken from the worst case, we can also say that n is the length of the string.
Space Complexity:
The space complexity of the above method will be O(m) when we consider the recursion space as the max height of stack will be equal to the height of the recursion tree i.e. m.
So, dear reader, we hope that you have understood the above solution completely. If you have any doubts about the procedure or the code, refer to the complete solution video to get more clarity. With this, we have completed this problem.
Here are some suggestions from our side that you do not want to miss:
We also suggest that you should make notes for these problems as we have a lot of similar problems in this set together and if you will not make notes it will become difficult for you to revise and you will have to watch the entire solution video or read the complete article again at the time of revising. So, do follow that suggestion. Till then, Happy Coding!!!
