Redirecting to
NADOS


  Prev   Next

Words - K Selection - 2







Champions keep playing until they get it right.
- Billie Jean King

Words - K Selection - 2

Welcome Back Reader!

In this article we will discuss about the next problem based on "Recursion and Backtracking" i.e. Words - K Selection - 2.

Prerequisite for this problem is Combination - 2 . If you have gone through this problem already then you might remember that we used to put r identical 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. Let's jump to the problem

Understanding the problem:

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

Given Word: aabbbcc

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.

Moving On:
  • Let us go through the rules again:
    1. All characters should be distinct.
    2. K distinct characters should be selected.

  • We will solve this question through recursion:
    1. We have n options to explore where n represents the number of distinct characters.
    2. Each nth level of the recursion deals with the placement of unique characters at index greater than the index of last placed element in the nth slot.

  • Base Case:
    1. 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:
img

At level-1, we have we have three options, we can choose a, b or c. Rest of the work is passed to Level-2.

At level-2, we have 2 ways to further explore a. It can either choose to be with b or c. Then we move to b, we have only one way to explore b, that is by appending c with it. Then we move to c, it has no option. And pass the rest of the work to level-3.

At level-3, we have crossed the value k (2) so we have no more options to explore as there are only 2 slots available. Since each level corresponds to filling each slot, we have already dealt with both the spots 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(String ustr, int cs, int ts, int lc, String asf)

  • 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 the hashset, all the values are stored in a string, ustr. This has been already done for us in the main.
  • cs: current selection; stores the count of characters selected so far in asf.
  • ts: total selections; its value is initialized with k and it remains fix.
  • ts: total selections; its value is initialized with k and it remains fix.
  • lc: (last choice) initialized with -1, represents last index which of the character which 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!

img
Code Explained:
  • Initially lc is -1, cs is 0 and asf is an empty string.
  • Then we use a for loop to explore the characters which occurs after lc till the length of ustr in ustr. And append this character in the asf, put i as lc and increment cs as one character has been added to asf.
  • For the base case we check if cs has crossed 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

Complexities:
Time Complexity:

O()

Space Complexity:

O()

import java.io.*; import java.util.*; public class Main { public static void generateSelection(String ustr, int cs, int ts, int lc, String asf) { if (cs > ts) { System.out.println(asf); return; } for (int i = lc + 1; i < ustr.length(); i++) { generateSelection(ustr, cs + 1, ts, i, asf + ustr.charAt(i)); } } 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 unique = new HashSet<>(); String ustr = ""; for (char ch : str.toCharArray()) { if (unique.contains(ch) == false) { unique.add(ch); ustr += ch; } } generateSelection(ustr, 1, k, -1, ""); } }
java; true";

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.

All the best for an exciting future!

Happy Coding!

Author: Nikita Aggarwal
 
Run
Id Name