A goal should scare you a little, and excite you a lot. - Joe Vitale
Max Score
Welcome back, dear reader. So, how is it going? In this article we will discuss the problem MAX SCORE. Have a look at the sample input to understand the problem.
Wait, what is this weird input and what do we have to do in this question? Let's see.
Problem Explanation:
We are given 4 in the first line of input and in the next line we are given 4 words. So, this much is clear to us. Now the first thing we have to do is create subsets of this set of 4 words. But, there is a condition to making these subsets. In the third line of input we are given a number 9 which indicates the size of a character array and in the next line, we have a character array of size 9. But, what are these characters?
This character array shows the frequency of these characters that can be present in the subset that we create. What do we mean by this? See, we are given 3 "d" characters in the character array. This means that the subset that we will make can have a maximum of 3 times the character "d"in it. For instance, we can have a subset {dog, dad} as the number of times "d" occurs in this subset is 3 which is equal to the max limit. But, we cannot have a subset like {dog, dad, good} as "d" occurs 4 times which is greater than the max limit of occurrence of "d".
So, now we know what kind of subsets we are allowed to make. But, we are still left with the last line of input. This line has 26 integers and these integers specify the score of each alphabet.
Now, we can calculate the score of a subset by adding the scores of all the alphabets in it. For instance:
So, there are many valid subsets and each valid subset will have a score. So, we have to print the maximum score out of the scores of the valid subsets. We hope that you have understood the question completely. If you have any doubts regarding the question, refer to the video MAXIMUM SCORE OF WORDS to understand the question completely. Now, let us discuss the approach to solve this problem.
Algorithm:
We will iterate through every word in the array and each word will have two choices- to be included in the subset or not to be included in the subset.
If the word is not included in the subset, the score of this word will be 0 and the total score will depend upon the further words in the array.
If the word has to be included, we must check whether it can be included or not according to the max limit of each character given to us.
If it can be included, its score will be calculated by summing the score of every letter in it and this score will be added to the overall score of the subset. Still, the total score will depend upon the next words in the subset.
Approach:
Let us start by applying the general idea of what can be done. Firstly, we should be clear with what we have to do. We have to give the maximum score out of the valid subsets of words. So, we know that we have to make subsets during this process. Now, there are two possibilities for every word. Either we can include it in the subset or we cannot. This can also be thought of as every word as two choices, whether to come into the subset or not.
So, for every word, we will make two recursive calls. One which tells us that this word is not included and the other which tells us that this word is included.
So, we are going to make two calls. One call will give us the score of the subset if the word which we are at (in the words array) is not included and the other call will tell us the score of the subset which includes the current word too.
So, let us have a look at the procedure and let us try to devise the code simultaneously.
To understand every possible case, let us say our index "idx" is currently as the position shown.
Dear reader, you need to understand carefully what all we have done when we are at the current position shown in the diagram. We have already visited two words and have calculated the scores of the subsets including and without including that word. This means that currently, we already have some subset to which we are deciding to add the word "dad".
So, we already have a score. Now, we want to see whether we should include the word dad or not. So, the first call is very simple. We simply move our index one step ahead and do not include the score of this word into our previous score.
So, in the recursive function signature given in the question, we are given an array of words and a frequency array and a score array of size 26 and the index that we are currently in. (The frequency array is also of size 26 and has the frequency of each character that we can have at every index)
Why not include this Word?
Now as discussed, we first want to calculate the score without including this word. Now, you might be thinking that if we will not include this word then definitely, the score will be less and we want to attain the maximum score. Well, you forgot that we still have words left in the words array and it might happen that the remaining words in the words array might give us the maximum score. So, yes, we have an option for not including this word and it is absolutely correct. So, if we don't include this word, what will be the score returned by this? Well, its own score will be zero since it is not included but it will make the recursive call for the process to repeat for the next words.
This means that its own score will be zero and the total score will now depend on the score which comes from the further words.
You may refer to the solution video to understand the above recurrence call that we have made.
So, this was when we were not including the word into the subset. Now, let us say we want to include the word into the subset. So, how will we go about it?
Including the word into the Subset
Let us recall our situation by looking at img-4 again.
So, we are at this position in the array and we now want to calculate the score by including the current word.
There were two possibilities or two options for every word i.e. to be included or not to be. Earlier, we calculated the score by not including the word. Now, we want to include the word but, it might happen that the word still does not get included in the subset. Why? This might happen if the word we are trying to include contains one or more characters whose frequency limit was already reached. So, if we try to include them, it will be an invalid subset. So, we have to count the score for inclusion of the word, only if it gets included.
See, when we might have included some words before this word into the subset, we would have changed the frequency of the characters in the frequency array. We already would have reduced the frequency of those characters which appear in the words below. So, now when we include another word, we will check each character of the word and see the frequency of this character in the frequency array. If the frequency for a particular character is already 0 and this character is present in our word which we have to include, we will not be able to include this word as the max limit of occurrence of that character would be crossed.
If the frequency for all the characters in the current word is such that we can include this word then, this word will be included. We also have to take care that there can be multiple instances of the same character in a word.
Let us say that we have a situation where we are allowed to repeat the character "d" 3 times at max. Let's say we have repeated it 2 times already and the word that we want to include is "dad". So, we will not be able to include it as it has 2 instances of character "d" and we will cross the max limit if we include it. So, we have to take care of this too.
Now if we include this word, the total score will become the score of the current word + the score of the further words.
Now, the maximum score is what we want, right? So, we will return the max score that will be the maximum out of the two scores that we have calculated, one including the current word and the other, without including the current word.
Don't forget to add the base case for recursion. What will be the base case? Well, we are traversing the array of words and deciding whether each word will come into the subset or not. So, if we reach the end of this array, we will have to return from here. This is the base case.
Base Case: When index becomes equal to the size of the words array i.e. when we have traversed the words array completely then we have no word left to include in the subset. Since there is no word left, the score that we get from here will be 0. So, when idx==word.length, return 0.
So, dear reader, we hope that you have understood the complete procedure. You may refer to the solution video to understand the above procedure and the code written below completely.
Java Code
import java.io.*;
import java.util.*;
public class Main {
public static int solution(String[] words, int[] farr, int[] score, int idx) {
if(idx==words.length)
{
return 0;
}
int sno=0 + solution(words,farr,score,idx+1); //score of the subset when the word is not included
int sword=0;
String word=words[idx];
boolean flag=true;
for(int i=0;i< word.length();i++)
{
char ch=word.charAt(i);
if(farr[ch-'a'] ==0)
{
flag=false;
}
farr[ch-'a']--;
sword += score[ch-'a'];
}
int syes=0; //score of the subset when the word is included
if(flag)
{
syes=sword+solution(words,farr,score,idx+1);
}
for(int i=0;i< word.length();i++)
{
char ch=word.charAt(i);
farr[ch-'a']++;
}
return Math.max(syes,sno);
}
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int nofWords = scn.nextInt();
String[] words = new String[nofWords];
for(int i = 0 ; i < words.length; i++) {
words[i] = scn.next();
}
int nofLetters = scn.nextInt();
char[] letters = new char[nofLetters];
for (int i = 0; i < letters.length; i++) {
letters[i] = scn.next().charAt(0);
}
int[] score = new int[26];
for (int i = 0; i < score.length; i++) {
score[i] = scn.nextInt();
}
if (words == null || words.length == 0 || letters == null || letters.length == 0 || score == null
|| score.length == 0) {
System.out.println(0);
return;
}
int[] farr = new int[score.length];
for (char ch : letters) {
farr[ch - 'a']++;
}
System.out.println(solution(words, farr, score, 0));
}
}
java;
true";
So, dear reader, we hope that you have understood the complete procedure. If you still have any doubts about the procedure or the code, you may refer to the complete solution video to clear all your doubts. Let us now discuss the time and space complexity of the above code.
Time and Space Complexity
Time Complexity:
The time complexity for the above solution is O(2n) where n is the number of input words. This is because we have n words and every word has two choices i.e. to be included in the subset or not to be. You might be thinking what about the validation that we applied? We are not generating 2n subsets, rather only the valid ones. Actually, this is not completely true. Backtracking generates all the possible subsets and we select the valid subsets from them. So, we are creating 2n subsets and hence the time complexity becomes 2n.
Space Complexity:
The space complexity of the above solution is O(h) where h is the height of the recursion stack and O(1) without considering the recursion space as we have not used any extra memory other than recursion.
So, dear reader, hope that you got the above solution completely and have also understood the time and space complexity analysis. If you still have any doubts regarding this problem, you should refer to the complete solution video to clear all your doubts. With this, we have completed this problem.
Suggestions:
Here are some suggestions from our side that you do not want to miss:
We recommend you watch the complete solution video at least once to get the entire concept with full clarity in your mind.
We also recommend that you dry run the code once with the procedure to understand what exactly is happening behind the scenes in the recursion. So, keep practicing and moving forward.
All the best for an exciting future!
Happy Coding!