Formatted question description: https://leetcode.ca/all/1255.html

1255. Maximum Score Words Formed by Letters

Level

Hard

Description

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.

Solution

First, calculate the available numbers of each letter according to letters. For example, if 'a' occurs twice in letters, then the available number of a is 2.

Then loop over all possible combinations of words, where each word is selected or not selected. For each combination, if it is possible, which means the selected words can be formed by using the given letters, then calculate the total score of the combination and maintain the maximum score.

Finally, return the maximum score.

class Solution {
    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        int maxScore = 0;
        int[] available = new int[26];
        for (char letter : letters)
            available[letter - 'a']++;
        int length = words.length;
        int states = 1 << length;
        for (int i = 1; i < states; i++) {
            int[] bits = numToBits(i, length);
            if (possible(words, bits, available)) {
                int curScore = calculateScore(words, bits, score);
                maxScore = Math.max(maxScore, curScore);
            }
        }
        return maxScore;
    }

    public int[] numToBits(int num, int length) {
        int[] bits = new int[length];
        for (int i = 0; i < length; i++) {
            bits[i] = num % 2;
            num /= 2;
            if (num == 0)
                break;
        }
        return bits;
    }

    public boolean possible(String[] words, int[] bits, int[] available) {
        int[] counts = new int[26];
        int length = words.length;
        for (int i = 0; i < length; i++) {
            if (bits[i] == 1) {
                String word = words[i];
                int wordLength = word.length();
                for (int j = 0; j < wordLength; j++) {
                    char letter = word.charAt(j);
                    counts[letter - 'a']++;
                    if (counts[letter - 'a'] > available[letter - 'a'])
                        return false;
                }
            }
        }
        return true;
    }

    public int calculateScore(String[] words, int[] bits, int[] score) {
        int totalScore = 0;
        int length = words.length;
        for (int i = 0; i < length; i++) {
            if (bits[i] == 1) {
                String word = words[i];
                int wordLength = word.length();
                for (int j = 0; j < wordLength; j++) {
                    char letter = word.charAt(j);
                    totalScore += score[letter - 'a'];
                }
            }
        }
        return totalScore;
    }
}

// OJ: https://leetcode.com/problems/maximum-score-words-formed-by-letters/
// 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;
    }
};

class Solution:
    def maxScoreWords(
        self, words: List[str], letters: List[str], score: List[int]
    ) -> int:
        cnt = Counter(letters)
        n = len(words)
        ans = 0
        for i in range(1 << n):
            cur = Counter(''.join([words[j] for j in range(n) if i >> j & 1]))
            if all(v <= cnt[c] for c, v in cur.items()):
                t = sum(v * score[ord(c) - ord('a')] for c, v in cur.items())
                ans = max(ans, t)
        return ans

func maxScoreWords(words []string, letters []byte, score []int) (ans int) {
	cnt := [26]int{}
	for _, c := range letters {
		cnt[c-'a']++
	}
	n := len(words)
	for i := 0; i < 1<<n; i++ {
		cur := [26]int{}
		for j := 0; j < n; j++ {
			if i>>j&1 == 1 {
				for _, c := range words[j] {
					cur[c-'a']++
				}
			}
		}
		ok := true
		t := 0
		for i, v := range cur {
			if v > cnt[i] {
				ok = false
				break
			}
			t += v * score[i]
		}
		if ok && ans < t {
			ans = t
		}
	}
	return
}

1255 - Maximum Score Words Formed by Letters

1255. Maximum Score Words Formed by Letters

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

1255. Maximum Score Words Formed by Letters

Level

Description

Solution

All Problems

All Solutions