## Algorithm

Problem Name: 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`, `score`, ... , `score` 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.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maxScoreWords = function (words, letters, score) {
const points = new Map()
const count = Array(26).fill(0)
for (let w of letters) {
count[w.charCodeAt(0) - 97] = ~~count[w.charCodeAt(0) - 97] + 1
}
return dfs(count, 0)
function dfs(count, index) {
if (index >= words.length) {
return 0
}
const x = dfs(count, index + 1)
const copy = [...count]
let point = 0
let isValid = true
for (let w of words[index]) {
let k = w.charCodeAt(0) - 97
copy[k]--
point += score[k]
if (copy[k] < 0) isValid = false
}
return Math.max(x, isValid ? point + dfs(copy, index + 1) : 0)
}
}
``````
Copy The Code &

Input

cmd
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

cmd
23

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
from collections import Counter as cnt

class Solution:
def maxScoreWords(self, w: List[str], l: List[str], s: List[int]) -> int:
def dfs(use, i):
return (
use
and i < len(w)
and max(
dfs(use, i + 1),
not cnt(w[i]) - use
and sum(s[ord(c) - ord("a")] for c in w[i])
+ dfs(use - cnt(w[i]), i + 1),
)
)

return int(dfs(cnt(l), 0))
``````
Copy The Code &

Input

cmd
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

cmd
23