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)

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?

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

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.