Perfection is achieved not when there is nothing more to add, but rather when there is nothing more to take away.
Words - K Selection - 4
Welcome Back Reader!
In this article we will discuss about the next problem based on "Recursion and Backtracking" i.e. Words - K Selection - 4.
Prerequisite for this problem is Words - K Selection - 2. If you have gone through this problem already then you might remember that we used to select k distinct characters from the given word. Current problem is almost similar to this one. The only difference is that k characters may not be necessarily distinct. So in this problem we will be using the same approach to solve it.
In the previous problem Words - K Selection - 3, we solved the exact same problem but with a different approach.
Before you move any further, it is advised that you give this problem a fair try.
In this problem you are given a word (may have one character repeat more than once) and an integer k.
All you need to do is generate and print all ways you can select k characters out of the word.
Note: Use the code snippet and follow the algorithm discussed in the video. The judge can't force you but intends you to teach a concept. Play in the spirit of the question.
Sample Input:
aabbbcc
2
Sample Output:
ab aa ac bb bc
(in different lines)
How?
Given Word: aabbbcc
K: 2
So we had to generate all ways in which 2 characters can be selected. And all such ways can be seen in the sample output.
For more clarity of the question; watch this part of the video.
Approach :
Moving On:
Let us go through the rules again:
Permutations are permitted.
K distinct characters should be selected.
We will solve this question through recursion:
We have n options to explore where n represents the number of distinct characters.
Each nth level of the recursion deals with the placement of unique characters at index greater than or equal to the index of last placed element in the nth slot.
Base Case:
When the level crosses the value of k.
Let's try to draw the recursion tree for an input, aabbbcc keeping the above points into consideration:
We basically explore the next or same characters to avoid permutation at each level. By this we mean for a we have all a, b and c in options. For b we have b and c in options. And for c only c. Each time we add an element to the answer string we deduce that character's count from the hashmap.
At level-1, we have three options, we can choose from a, b or c. Rest of the work is passed to Level-2.
At level-2, we have again 3 ways to further explore a. It can either choose to be with a, b or c as all three are available.
Then we move to b, we have two ways to explore b, that is by appending either b or c with it as both are available at this stage.
Then we moved to c, there was only one option to explore as there is only one c and that has already been used. We are out of this option as well.
And pass the rest of the work to level-3.
At level-3, we have again 5 ways to explore in total and decide which of them are eligible to make further calls. We use the same trick to do so and then after deciding we pass the rest of the work to the next level.
At level-4, we have crossed the value k (3) so we have no more options to explore as there are only 3 slots available. Since each level corresponds to filling each slot, we have already dealt with all three slots in previous levels.
So here, we simply print the obtained answers.
For more clarity; watch this part of the video lecture.
Signature of the function:
public static void generateSelection(int cs, int ts, String ustr, HashMap< Character, Integer> unique, int ls, String asf)
cs: current selection; stores the count of characters selected so far in the asf and is initialized to 0.
ts: total selections; its value is initialized with k and it remains fixed.
ustr: unique string; contains all the distinct characters of the input string.Using a hashset, all the unique values are collected from the input string and then using a for loop on hashset, all the values are stored in a string, ustr. This has been already done for us in the main.
unique: a hashmap storing the frequency of each distinct character.
ls: (last selected character's index) initialized with 0, represents the last index of the character which was used.
asf: answer so far; string type. Stores the answer explored till this point. Updated it at each level by appending a character from ustr.
Let's try to code this!
Code Explained:
Initially ls is 0, cs is 0 and asf is an empty string.
Then we use a for loop to explore the characters which occur at ls or after ls till the length of ustr in ustr.
And then check its frequency in the hashmap, if if the frequency of the character is greater than 0 then first we decrement the frequency, corresponding to this character and then finally make a recursive call by appending this character in the asf, puting i as lc and incrementing cs as one character has been added to asf.
In postorder we undo the frequency by incrementing it again.
For the base case we check if cs becomes equal to ts, if it has then it means we have selected an element for each position.
Then we print the asf and finally return.
For better understanding of the code, watch this part of the video.
import java.io.*;
import java.util.*;
public class Main {
public static void generateSelection(int cs, int ts, String ustr, HashMap< Character, Integer> unique, int ls, String asf) {
if (cs > ts) {
System.out.println(asf);
return;
}
for (int i = ls; i < ustr.length(); i++) {
char ch = ustr.charAt(i);
if (unique.get(ch) > 0) {
unique.put(ch, unique.get(ch) - 1);
generateSelection(cs + 1, ts, ustr, unique, i, asf + ch);
unique.put(ch, unique.get(ch) + 1);
}
}
}
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());
HashMap< Character, Integer> unique = new HashMap< >();
String ustr = "";
for (char ch : str.toCharArray()) {
if (unique.containsKey(ch) == false) {
unique.put(ch, 1);
ustr += ch;
} else {
unique.put(ch, unique.get(ch) + 1);
}
}
generateSelection(1, k, ustr, unique, 0, "");
}
}
java;
true";
Analysis
Time Complexity:
O(kn)
Space Complexity:
O(k)
We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.
Trust me it will just get easier to understand after you have watched the solution video.
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem.
