A language that doesn't affect the way you think about programming is not worth knowing.
Words-K Length Words-1
Welcome back, dear reader. In this article we will discuss this problem called WORDS-K LENGTH WORDS-1. 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.
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 the 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 told 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. Let us recall what we used to do in the boxes and items problem with the help of Euler tree and what we used to keep on the different levels and what used to be our different options.
So, let us say we have three boxes and we have to place 2 unique items to put into these boxes. So, we will keep our boxes at the levels.
As you can see in the img-4, the 0th level corresponds to the box 1 i.e. what all options do we have for box 1. We can either not add any element to the first box, or we can add item1 to the first box or we can add item 2 to it. So, the boxes are at the levels and the options are the items.
Can you think of why we chose the boxes to be kept at levels and the items to become the options for us? This is just because we are learning this method of solving the problem. The same problem can be solved by keeping the items at the levels and the boxes will become the options for us. We will learn the second method in the next question K-LENGTH WORDS-2. Right now, let us focus back on our first method only.
At the next level, we have box 2. There, we have again various options. Let us see what options we have:
So, when we did not select any item in the level 0, we had three options for box 2 in the next level i.e. not to put any item or to put item 1 or the item 2..
On the other hand, if we already had kept the item1 in the first box, we have only two options at level 2. We can either not keep the item 2 in the second box or we can keep it. The same goes for the situation when we had kept the item 2 in the first box at the previous level.
So, dear reader, we hope that you understand what we are trying to do here. We have options for the boxes that we are filling at each level. Try to finish the next level of the tree yourself and get the final combinations. The final combinations that you will get are already shown in img-2. We recommend you refer to the solution video.
Now, in our question, how will we use this levels and options method?
In our question, the number of unique characters will always be greater than the length of the words to be formed. Why? This is because if the number of unique characters is less than the length of the words to be formed, we will have to repeat the characters in the word and we do not want to do that.
So, actually the characters have a choice here i.e. to go at a particular spot or not to go there. We agree that you might think that the spots have a choice to choose a character from the unique characters but if you think carefully, this is not much of a choice. We will have to choose one of the characters from the given characters whereas, if we keep characters at the level then we have a choice of whether to keep them at a particular spot or not and if to keep them, where to keep them. So, we have a vast choice when we choose the characters to represent the levels rather than the spots.
Before moving forward, let us once more understand what these characters and spots are.
What are characters and spots?
We have the input string "abcabc". From this string, we have to make words of length 2 with all characters unique. So, the unique characters in this string are 'a', 'b' and 'c'. We have two spots. These two spots are for the two letter words that we have to create. So, at each spot, we can have one character out of the 3 distinct characters.
Now, as we have already decided, let us put each distinct character at each level of the tree and try to find out the options of the spots it can go to.
Let us take the first unique character 'a'. It has three options. First, not to go at any spot, the second to go at spot1 and the third to go at the 2nd spot. These are shown in the figure below:
So, if 'a' does not go at any spot, we have both the spots empty whereas if it goes at any one spot, the other will be empty. Now, let us see what options we have for character 'b'.
So, the above diagram shows the choice of spots for character 'b' at different levels. We hope that you have understood the levels and options and how we are deciding what to keep at a level and what all options to have. We recommend you watch the solution video to understand the concept clearly and also, why we chose the characters at levels and the spots as the options. We also recommend you try to make the rest of the tree on your own and find all the combinations. The tree will look like this:
So, dear reader, we hope that you have understood the procedure till here. Now that we have understood the complete procedure, let us quickly overview the procedure and how we are going to implement this in the code and then we will write the code as well.
What will we 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 apply the loop for the number of spots i.e. the length of the words that we have to make and in that loop, we will see whether a spot is occupied or not. If it is unoccupied, we will occupy it with a character and we will apply the recursive call for the next character to be occupied.
Do not forget to apply the "no" call as well i.e. a character was not placed at any spot. Also, this solution uses backtracking so you have a hint of what to do. Think about this!!!
Now that we know the complete procedure and have an idea of what we have to do, we can now write the complete code.
import java.io.*;
import java.util.*;
public class Main {
public static void generateWords(int cc, String ustr, int ssf, int ts, Character[] spots) {
if (cc == ustr.length()) {
if(ssf == ts){
for(int i = 0; i < spots.length; i++){
System.out.print(spots[i]);
}
System.out.println();
}
return;
}
char ch = ustr.charAt(cc);
for(int i = 0; i < spots.length; i++){
if(spots[i] == null){
spots[i] = ch;
generateWords(cc + 1, ustr, ssf + 1, ts, spots);
spots[i] = null;
}
}
generateWords(cc + 1, ustr, ssf + 0, ts, spots);
}
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;
}
}
Character[] spots = new Character[k];
generateWords(0, ustr, 0, k, spots);
}
}
java;
true";
So, dear reader, we hope that you have understood the above code completely. If you have any doubts regarding it, refer to the solution video to understand the complete code and clear all your doubts. Let us now discuss the time and space complexity of the above method.
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 n levels in the tree and at every level, the maximum choices that we have is m+1.
Best Case: If the input string has all the characters the same then the number of unique characters is 1. Also, in such a case, we can not make a word of more than 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 if 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 the 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(n) when we consider the recursion space as the max height of the stack will be equal to the height of the recursion tree i.e. n.
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:
It is very important that you spend some time meditating on the fact that why we chose the one with more count i.e. the unique characters in this case over the spots and the boxes over the items to be kept at the levels.
We suggest that you try to find the time complexity and the space complexity by mathematical analysis too. This will help build your concepts stronger. So, till then, keep practicing. Happy Coding!!!
