Optimism is an occupational hazard of programming: feedback is the treatment.
~Kent Beck
Words - K Selection - 3
Welcome Back Reader!
In this article we will discuss about the next problem based on "Recursion and Backtracking" i.e. Words - K Selection - 3.
Prerequisite for this problem is Words - K Selection - 1. 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.
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:
aa ab ac bb bc cc
(in different lines)
How?
Given Word: aabbbcc
K: 2
So we had to generate all ways in which 2 characters can be selected from the given word. 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 restricted i.e. do not arrange the selection.
Any K characters should be selected from the given word.
We will solve this question through recursion:
We will have these options - whether we can not include the character in the answer at all or we have the option to include it 1 to f (frequency of that character) times.
Each ith level of the recursion deals with placement of the frequency of the distinct i'th character.
Base Case:
When the i touches the count of distinct characters then we check if length of the answer string equal to k and if yes then it becomes eligible for the output.
Let's try to draw the recursion tree for an input, aabbac keeping the above points into consideration:
There are 3 a, 2 b and 1 c in the given string. We store this information in a hash map.
At level-1, we deal with a, we have four options that correspond to a; we can either add all the 3 'a' or 2 'a' or 1. We can also choose to not add 'a' at all. Rest of the work is passed to Level-2 which takes b into account.
At level-2, we deal with b, we have three options that correspond to b; we can either add both the bs or 1. We can also choose to not add 'b' at all. We have these options for all the ways that were explored by 'a'. Rest of the work is passed to Level-3 which takes c into account.
At level-3, we deal with c, we have two options that correspond to c; we can either add the single 'c' or not add 'c'. We have these options for all the ways that were explored by 'b'. Rest of the work is passed to Level-4.
At level-4, we have no more options to explore as there are only 3 characters in the hashmap. Since level corresponds to each character, we have already dealt with all 3 characters (a, b, c) in previous levels.
So here, we check which of the possible answers is valid.
If the length of answer is equal to 3 (k) then it qualifies for the valid answers.
For more clarity; watch this part of the video lecture
Signature of the function:
public static void generateSelection(int cc, String ustr, int ssf, int ts, HashMap< Character, Integer> unique, String asf)
cc: input array of length n.
ustr: unique string; contains all the distinct characters of the input string.In the main, using a hashset, all the unique values are collected from the input string and then using a for loop on the hashset, all the values are stored in a string, ustr.
ssf: selection so far; stores the count of characters selected so far in asf.
ts: total selections; its value is initialized with k and remains fixed.
unique: a hashmap storing the frequency of each distinct character.
asf: answer so far; string type. Stores the answer explored till this point. Updated it at each level if required.
Let's try to code this!
Code Explained:
Initially i is 0, ssf is 0 and asf is an empty string.
If (n - 1) characters can be permuted into k slots, then the nth element can either join the answer or not.
We have to consider two cases at every level:
Case 1: it joins the answer.
Case 2: it does not join the answer.
If the ith character of ustr decides to join then a call is made to the next level ( i+1) and ch is appended in the asf (Case 1). As the number of characters in asf is increased, therefore, we will increase ssf in this case.
If the ith character of ustr (ch) decides not to join asf then a call is made to the next level (i+1) without any other change (Case2). As the number of characters remains same in asf, we do not increase ssf.
For the base case we check if i has become equal to utsr.length, if it does then it means we have permuted all the elements of the utsr in asf. Then we will check if ssf is equal to the ts, this condition filters out the answers in which there is an empty slot.
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 cc, String ustr, int ssf, int ts, HashMap< Character, Integer> unique, String asf) {
if (cc == ustr.length()) {
if(ssf == ts){
System.out.println(asf);
}
return;
}
char ch = ustr.charAt(cc);
for(int i = unique.get(ch); i > 0; i--){
char[] fasf = new char[i];
Arrays.fill(fasf, ch);
generateSelection(cc + 1, ustr, ssf + i, ts, unique, asf + new String(fasf));
}
generateSelection(cc + 1, ustr, ssf + 0, ts, unique, asf);
}
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(0, ustr, 0, k, unique, "");
}
}
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.
