Leetcode 1255. Maximum Score Words Formed by Letters

Problem Explanation:

The given problem is an optimization problem, where we are given a list of words and their corresponding costs. We are interested in finding out the maximum cost that can be obtained by forming words from the given list.

In order to solve this problem, we have to use a combination of different words and return the one with the maximum score.

Let's walk through an example to understand this problem:

Suppose, we have the following input:

1
2
3words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]

In this case, score of 'a' is 4, 'b' is 4, 'c' is 4, 'x' is 5, and 'z' is 10. Given the letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27 (4+5+4+5+4+5). The word "xxxz" will only give a score of 25. Hence, the output will be 27.

Solution Approach:

The problem can be solved by using Depth-First Search (DFS) algorithm. The main idea is to iterate over all the words and for each word, attempt to reduce the count of its characters from the given letters. After reducing the counts, we recursively try forming other words and keep track of the maximum score that can be formed.

Here's a high-level view of how this solution works:

1. Initialize a count array to keep track of the frequency of each letter.
2. Loop through the words to try using each word.
3. For each word, reduce the count of its letters and calculate the score earned.
4. Recursively try using the next words with the updated count array.
5. Get the maximum score among the trials.

Algorithm Steps:

1. Create an array 'count' of size 26 to store the count of each letter in 'letters'.
2. Call a recursive function 'dfs' with the initial arguments as 'words', 0, 'count', 'score'. The function 'dfs' base case will be to return 0 when it reaches the end of the words array.
3. Within 'dfs', use a loop to iterate each remaining word in 'words'. For each word, check if it's valid to use the word by reducing the count of its characters in 'count'.
4. If it's valid to use the word, recursively call the 'dfs' function with the next word and the updated 'count' array, and update the maximum score so far.
5. After trying to use a word, restore the 'count' array to its previous state.
6. Return the maximum score obtained.

Python Solution

1
2python
3class Solution:
4    def maxScoreWords(self, words, letters, score):
5        count = [letters.count(chr(ord('a') + k)) for k in range(26)]
6        
7        def dfs(i, count):
8            if i == len(words):
9                return 0
10            ignore = dfs(i + 1, count)
11            cnt = [0] * 26
12            for c in words[i]:
13                cnt[ord(c) - ord('a')] += 1
14            if all(cnt[k] <= count[k] for k in range(26)):
15                for k in range(26):
16                    count[k] -= cnt[k]
17                include = sum(cnt[k] * score[k] for k in range(26)) + dfs(i + 1, count)
18                for k in range(26):
19                    count[k] += cnt[k]
20                return max(ignore, include)
21            else:
22                return ignore
23        
24        return dfs(0, count)

Java Solution

1
2java
3class Solution {
4    public int maxScoreWords(String[] words, char[] letters, int[] score) {
5        int[] alphabet = new int[26];
6        for (char c : letters) {
7            alphabet[c - 'a'] += 1;
8        }
9        return dfs(words, score, alphabet, 0);
10    }
11
12    private int dfs(String[] words, int[] score, int[] alphabet, int index) {
13        if (index >= words.length) return 0;
14        int skip = dfs(words, score, alphabet, index + 1);
15        int earned = 0;
16        for (char c : words[index].toCharArray()) {
17            alphabet[c - 'a']--;
18            earned += score[c - 'a'];
19        }
20        int takeCurrent = 0;
21        if (isValid(alphabet)) {
22            takeCurrent = earned + dfs(words, score, alphabet, index + 1);
23        }
24        for (char c : words[index].toCharArray()) {
25            alphabet[c - 'a']++;
26        }
27        return Math.max(skip, takeCurrent);
28    }
29
30    private boolean isValid(int[] alphabet) {
31        for (int i = 0; i < 26; i++) {
32            if (alphabet[i] < 0) return false;
33        }
34        return true;
35    }
36}

JavaScript Solution

1
2javascript
3var maxScoreWords = function(words, letters, score) {
4    let total = Array(26).fill(0);
5    for(let l of letters) total[l.charCodeAt() - 97] += 1;
6    
7    function dfs(idx, total) {
8        if (idx === words.length) return 0;
9        let res = dfs(idx+1, total);
10        let current = Array(26).fill(0);
11        for(let c of words[idx]) {
12            current[c.charCodeAt() - 97] += 1;
13            total[c.charCodeAt() - 97] -= 1;
14        }
15        let sum = 0, valid = true;
16        for(let i = 0; i < 26; i++) {
17            if(total[i] < 0) valid = false;
18            sum += current[i]*score[i];
19        }
20        if(valid) res = Math.max(res, sum + dfs(idx+1, total));
21        for(let c of words[idx]) total[c.charCodeAt() - 97] += 1;
22        return res;
23    }
24    return dfs(0, total);
25};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int dfs(vector<string>& words, int start, vector<int>& freq, vector<int>& score) {
6        if (start >= words.size()) return 0;
7
8        int skip = dfs(words, start + 1, freq, score);
9
10        int currScore = 0;
11        bool valid = true;
12        for (char c : words[start]) {
13            freq[c - 'a']--;
14            currScore += score[c - 'a'];
15            if (freq[c - 'a'] < 0)
16                valid = false;
17        }
18
19        int take = 0;
20        if (valid)
21            take = currScore + dfs(words, start + 1, freq, score);
22
23        // undo the selections
24        for (char c : words[start])
25            freq[c - 'a']++;
26
27        return max(skip, take);
28    }
29    
30    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
31        vector<int> freq(26, 0);
32        for (char c : letters) freq[c - 'a']++;
33        return dfs(words, 0, freq, score);
34    }
35};

C# Solution

1
2csharp
3public class Solution {
4    public int MaxScoreWords(string[] words, char[] letters, int[] score) {
5        int[] count = new int[26];
6        foreach (char c in letters) {
7            count[c - 'a']++;
8        }
9        return Dfs(words, count, score, 0);
10    }
11
12    private int Dfs(string[] words, int[] count, int[] score, int index) {
13        if (index == words.Length) {
14            return 0;
15        }
16        int skip = Dfs(words, count, score, index + 1);
17        int currScore = 0;
18        bool valid = true;
19        foreach (char c in words[index]) {
20            count[c - 'a']--;
21            currScore += score[c - 'a'];
22            if (count[c - 'a'] < 0) {
23                valid = false;
24            }
25        }
26        int take = valid ? currScore + Dfs(words, count, score, index + 1) : 0;
27        foreach (char c in words[index]) {
28            count[c - 'a']++;
29        }
30        return Math.Max(skip, take);
31    }
32}

In the given solutions, we are applying a depth-first search to get the maximum possible score. To do this, we are iterating over all the words, and for each word, we are attempting to reduce the count of its characters from the given letters. After reducing the counts, we are recursively trying to form other words and keep track of the maximum score that can be formed. If it is not possible to use the current word, we just ignore it and move to the next word. After checking or using a word, we undo its effect from the count array for the next trials.

Time and Space Complexities

Time Complexity: The time complexity of this approach is O(N * 2^N), where N is the number of words. Here, we are visiting every node twice, once for considering the word and once for not considering the word, therefore making it a 2^N multiplication factor.

Space Complexity: The space complexity is O(N), which is needed for the recursion stack. The recursion depth can go down to N levels.

Optimizations:

There are a few ways we can optimize this solution.

First, we can sort the words by their scores in descending order before initiating the DFS. This way, we will first consider the words that give higher scores. We will still need to check all possible combinations of words, but for practical applications where we might stop the search process as soon as we find a valid combination, starting with the words that give higher scores will likely produce the best results early on.

Second, we can stop DFS if the score we have accumulated so far plus the maximum remaining achievable score is less than the current maximum score we have encountered. This is possible due to the sorting of words based on their scores.

Third, instead of using a depth-first search, we could use dynamic programming to solve this problem more efficiently. We could create a DP table where dp[i][j] represents the maximum score we can get by considering the first i words either completely or partially while staying within the limit of j letters. This approach would likely bring down the time and space complexity but would be more challenging to implement.

By implementing these improvements, we can develop faster and more efficient solutions for this problem.