1255

1255. Maximum Score Words Formed by Letters (Hard)

Given a list of words, list of  single letters (might be repeating) and score of every character.

Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).

It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', ... ,'z' is given by score[0], score[1], ... , score[25] respectively.

 

Example 1:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [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]
Output: 23
Explanation:
Score  a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23.
Words "dad" and "dog" only get a score of 21.

Example 2:

Input: words = ["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]
Output: 27
Explanation:
Score  a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27.
Word "xxxz" only get a score of 25.

Example 3:

Input: words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
Output: 0
Explanation:
Letter "e" can only be used once.

 

Constraints:

• 1 <= words.length <= 14
• 1 <= words[i].length <= 15
• 1 <= letters.length <= 100
• letters[i].length == 1
• score.length == 26
• 0 <= score[i] <= 10
• words[i], letters[i] contains only lower case English letters.

Companies:
Amazon, Google

Related Topics:
Array, String, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask

Solution 1. Bitmask

// OJ: https://leetcode.com/problems/maximum-score-words-formed-by-letters/
// Author: github.com/lzl124631x
// Time: O(2^N * NC + NW) where `N` is the length of `A`, `C` is the range of characters, and `W` is the maximum length of `A[i]`.
// Space: O(NC)
class Solution {
public:
    int maxScoreWords(vector<string>& A, vector<char>& letters, vector<int>& score) {
        int avail[26] = {}, ans = 0, cnt[14][26] = {}, N = A.size();
        for (char c : letters) avail[c - 'a']++;
        for (int i = 0; i < N; ++i) {
            for (char c : A[i]) cnt[i][c - 'a']++;
        }
        for (int m = 1; m < 1 << N; ++m) {
            int total[26] = {};
            for (int i = 0; i < N; ++i) {
                if (m >> i & 1) {
                    for (int j = 0; j < 26; ++j) total[j] += cnt[i][j];
                }
            }
            int i = 0;
            for (; i < 26 && total[i] <= avail[i]; ++i);
            if (i < 26) continue;
            int val = 0;
            for (int i = 0; i < 26; ++i) val += total[i] * score[i];
            ans = max(ans, val);
        }
        return ans;
    }
};

Solution 2. Bitmask DP

We can also use DP but for this problem it's slower and takes more space.

// OJ: https://leetcode.com/problems/maximum-score-words-formed-by-letters/
// Author: github.com/lzl124631x
// Time: O(2^N * C)
// Space: O(2^N * C)
class Solution {
public:
    int maxScoreWords(vector<string>& A, vector<char>& letters, vector<int>& score) {
        int avail[26] = {}, ans = 0, cnt[14][26] = {}, wordScore[14] = {}, N = A.size();
        vector<array<int, 26>> used(1 << N);
        vector<int> scoreSum(1 << N);
        for (char c : letters) avail[c - 'a']++;
        for (int i = 0; i < N; ++i) {
            for (char c : A[i]) {
                cnt[i][c - 'a']++;
                wordScore[i] += score[c - 'a'];
            }
        }
        for (int m = 1; m < 1 << N; ++m) {
            int lb = m & -m, i = __builtin_ctz(lb);
            used[m] = used[m - lb];
            for (int j = 0; j < 26; ++j) used[m][j] += cnt[i][j];
            int j = 0;
            for (; j < 26 && used[m][j] <= avail[j]; ++j);
            if (j < 26) continue;
            scoreSum[m] = scoreSum[m - lb] + wordScore[i];
            ans = max(ans, scoreSum[m]);
        }
        return ans;
    }
};