Maximum Score from Words Using a Letter Pool
You have a bag of letter tiles and a per-letter score. Pick a subset of allowed words to spell; each tile is consumed once. Maximize the total score of the words you can fully form.
Problem
Given a list words, an array letters (the available letters, each usable once), and an array score of length 26 (score[i] is the value of letter 'a'+i), return the maximum total score of any subset of words that can be formed using the available letters. A word's score is the sum of its letters' scores; a word can only be used if all its letters are available.
Input
A list words, an array letters of characters, and an array score of 26 integers.
Output
An integer: the maximum achievable total score.
Constraints
- 1 <= words.length <= 14
- 1 <= letters.length <= 100
- 0 <= score[i] <= 10; words and letters are lowercase.
Examples
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
Using 'dad' (5+1+5=... ) and 'good' yields the max total 23.
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,0,0,5]
Output
27
Choosing 'ax','bx','cx' beats using 'xxxz'.