Maximum Score Words Formed by Letters

lcpy gen -n 1255   # by problem number
lcpy gen -s maximum_score_words_formed_by_letters   # by problem name

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.

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.

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.

from collections import Counter


class Solution:
    def max_score_words(self, words: list[str], letters: list[str], score: list[int]) -> int:
        word_counts = [Counter(word) for word in words]
        word_scores = [
            sum(score[ord(c) - 97] * cnt for c, cnt in Counter(word).items()) for word in words
        ]
        n = len(words)

        def backtrack(i: int, available: Counter) -> int:
            if i == n:
                return 0
            best = backtrack(i + 1, available)
            counts = word_counts[i]
            if all(available[c] >= cnt for c, cnt in counts.items()):
                for c, cnt in counts.items():
                    available[c] -= cnt
                best = max(best, word_scores[i] + backtrack(i + 1, available))
                for c, cnt in counts.items():
                    available[c] += cnt
            return best

        return backtrack(0, Counter(letters))