Max Score

1. You are given a list of words, a list of alphabets(might be repeating) and score of every alphabet 
     from a to z.
2. You have to find the maximum score of any valid set of words formed by using the given 
     alphabets.
3. A word can not be used more than one time.
4. Each alphabet can be used only once. 
5. It is not necessary to use all the given alphabets.

Note -> Check out the question video and write the recursive code as it is intended without 
               changing signature. The judge can't force you but intends you to teach a concept.

Input Format

A number N representing number of words
N space separated strings
A number M representing number of alphabets(might be repeating)
M space separated characters
26 numbers representing score of unique alphabets from a to z.

Output Format

Check the sample ouput and question video.

Question Video Constraints

1 <= N <= 14
1 <= length of word <= 15
1 <= M <= 100
1 <= Value of score <= 10

Sample Input

4
dog cat dad good
9
a b c d d d g o o
1 0 9 5 0 0 3 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0

Sample Output

23

• Editorial

  Here the score of 'a' is 1 , 'b' is 0, 'c' is 9 ........ score of z is '0'.

  If we chose "dad" and "good" from the given set of words, our score will be -

  5(d) + 1(a)  + 5(d)      =          11

  3(g) + 2(o)  + 2(o) + 5(d)   =  12

       =  23 (maximum score possible)

  We can observe in total, we choose 'd' 3 times, 'o' 2 times, 'a' 1 time and 'g' 1 time.

  Also the given set of alphabets had at least 3 d's , 2 o's , a single 'a' and 'g'. Therefore, we did not choose more than given alphabets.

  We also have to make sure that we chose a single word at a time. Like we do not try to choose 'dad' 2 times,if it is available only one time in the list.

  We will store the frequency of the given alphabets in an array. Let us call this array far.

  freq[0]  = 1 , means there is one 'a' available.

  freq[25] = 5 , means there are 5 'z' available.

  Signature of the function -

  public static int solution(String[] words, int[] farr, int[] score, int idx)

  words - list of given words.

  farr - frequency array

  score - score corresponding to each alphabet.

  idx - current index in the words array.

  Then with the help of recursion, we will make two choices -

  1. YES CALL - Including the current word. We have to make sure that the every alphabet of the current word is present in the list of input alphabets, then only we can make a YES CALL.

  2. NO CALL - Not including the current word.

  We will return the max of both YES and NO call as we need the maximums score.

  Code -

  public static int solution2(String[] words, int[] farr, int[] score, int idx) {
                                  	if (idx == words.length) {
                                  		return 0;
                                  	}		
                                  	int max1 = solution2(words, farr, score, idx + 1);
                                  	int max2 = 0;
                                  
                                  	boolean isValid = true;
                                  	int scoreofCW = 0;
                                  	for (char ch : words[idx].toCharArray()) {
                                  		farr[ch - 'a']--;
                                  		if (farr[ch - 'a'] < 0) {
                                  			isValid = false;
                                  		}
                                  		scoreofCW += score[ch - 'a'];
                                  	}
                                  	if (isValid) {
                                  		max2 = solution2(words, farr, score, idx + 1);
                                  		max2 += scoreofCW;
                                  	}
                                  	for (char ch : words[idx].toCharArray()) {
                                  		farr[ch - 'a']++;
                                  	}
                                  	return Math.max(max1, max2);
                                  }

  java false

  Code explained -

  max1 is the NO CALL. We increase the current index and not include the current word from the words array in our answer.

  For the YES CALL,we will create a flag, if the flag is true then only we can make a YES CALL.We traverse through the current word and check whether each character of the current word is available in the freq array. If it is available we decrease it by one. If we find the frequency of the current character is less than 0, it means that we have used more than available,which means we cannot choose the current word. We will set our flag to false. Also in one more variable we will add the score corresponding to the each character of word.

  If the flag is TRUE, we will make a YES CALL and add the score to it.

  max2 is the YES CALL here.

  In the post order, we will increase the frequency of every character in the word, that we decreased in the pre order.

  We will return the maximum of max1 and max2 as we want the maximum answer. We don't know whether the maximum answer will be from including the current word or not, that is why we take maximum of both the cases.

  Base case -

  If the idx is equal to the length of the words array, we will return 0 as no word is left to be chosen.

• Asked in Companies
• Related Topics