There is only one thing that makes a dream impossible to achieve: the fear of failure.
Words - K Selection - 1
Welcome Back Reader!
In this article we will discuss about the next problem based on "Recursion and Backtracking" i.e. Words - K Selection - 1.
Prerequisite for this problem is Combination - 1. If you have gone through this problem already then you might remember that we used to place r items in n boxes. Current problem is quite similar to this one.
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 distinct 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 ac bc
(in different lines)
How?
Given Word: aabbbcc
Distinct characters: a b c
K: 2
So we had to generate all ways in which 2 distinct 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:
All characters should be distinct.
K distinct characters should be selected for each possible way.
We will solve this question through recursion and backtracking:
We will have these options - whether we can not include the character in the answer or not.
Each ith level of the recursion deals with placement of the distinct ith character.
Base Case:
When the i touches the count of distinct characters then we check if either of the slots in the answer string is empty or not and if it's not empty then it becomes eligible for the output.
Let's try to draw the recursion tree for an input, aabbbcc keeping the above points into consideration:
At level-1, we have two options for a, we can either choose to add a or not. We explore both the options and pass the rest of the work to level 2.
At level-2,we have two options for b, we can either choose to add b or not. We explore both the options for both the previous cases. We explore each way and pass the rest of the work to level 3.
At level-3,we have two options for c, we can either choose to add c or not. We explore both the options for all the previous cases. We explore each way and pass the rest of the work to level 4.
At level-4, we have no more options to explore as there are only 3 distinct characters. Since level corresponds to each distinct 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 any of the answer's length is not equal to k then we discard it from the answers. And the rest of them qualify as valid answers so we print them.
For more clarity; watch this part of the video lecture.
Signature of the function:
public static void generateSelection(int i, String ustr, int ssf, int ts, String asf)
i: 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.
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 i, String ustr, int ssf, int ts, String asf) {
if (i == ustr.length()) {
if(ssf == ts){
System.out.println(asf);
}
return;
}
char ch = ustr.charAt(i);
generateSelection(i + 1, ustr, ssf + 1, ts, asf + ch);
generateSelection(i + 1, ustr, ssf + 0, ts, 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());
HashSet< Character> unique = new HashSet< >();
String ustr = "";
for (char ch : str.toCharArray()) {
if (unique.contains(ch) == false) {
unique.add(ch);
ustr += ch;
}
}
generateSelection(0, ustr, 0, k, "");
}
}
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.
