# 1255. Maximum Score Words Formed by Letters

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.

# Solution

Approach 1: backtracking -- use the letters to construct words. Optimizations: pruning -- precompute the score for each word, and prune the branch where score_so_far + sum(words_score[i:]) <= self.max_score. And sum(words_score[i:]) can also be precomputed as a suffix sum.

# Code (Python)

Approach 1:

import collections
class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        # backtracking -- use the letters to construct words
        return self._backtrack(0, collections.Counter(letters), words, 0, score)
        # optimizations: pruning. Precompute the score for each word, and prune the branch where score_so_far + sum(words_score[i:]) <= self.max_score 
        # sum(words_score[i:]) can also be precomputed as a suffix sum
    
    def _backtrack(self, index, letters, words, score_so_far, scores):
        if index == len(words):
            return score_so_far
        
        max_score = 0
        # include words[index]
        can_form = True
        word_counts = collections.Counter(words[index])
        for letter, freq in word_counts.items():
            if letters[letter] < freq:
                can_form = False
                break
        if can_form:
            for letter, freq in word_counts.items():
                letters[letter] -= freq
            max_score = max(max_score, self._backtrack(index + 1, letters, words, score_so_far + sum(scores[ord(letter) - ord('a')] for letter in words[index]), scores))
            for letter, freq in word_counts.items():
                letters[letter] += freq
        # not include words[index]
        max_score = max(max_score, self._backtrack(index + 1, letters, words, score_so_far, scores))
        
        return max_score

# Code (C++)

Approach 1:

Approach 2: