Maximum Score Words Formed by Letters
Hard · Backtracking · Array · String · Dynamic Programming · Backtracking · Bit Manipulation · Bitmask
Problem
You are given a list of words, a list of single-letter tiles letters (letters may repeat), and an array score of length 26: score[0] is the value of a, score[1] of b, and so on up to z.
Choose a set of words to spell, using each word at most once and each tile at most once. You do not have to use every tile. The score of a set is the total value of all letters in the chosen words.
Return the highest score any valid set of words can reach.
Examples
Input: words = ["cat","act","tab"], letters = ["a","c","t","b","t"], score = [1,3,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0] Output: 8
There is only one a, so only one word can be spelled. tab is worth 4 + 1 + 3 = 8, the most of the three.
Input: words = ["hi","hello"], letters = ["h","i"], score = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] Output: 2
Only hi can be spelled from the two tiles.
Constraints
- 1 <= len(words) <= 14
- 1 <= len(words[i]) <= 15
- 1 <= len(letters) <= 100
- len(score) == 26
- 0 <= score[i] <= 10
- words[i] and letters[i] are lowercase English letters
Approaches
- Baseline: every subset, letters recounted — time O(2^n · n · L), space O(26)
Follow-up
What if you wanted the most words rather than the most points, or exactly k words? The same search with a different value or an extra counter answers both: see the use cases “Spell as many words as possible” and “Best score using exactly k words”.
Related problems
Start free on Cariara · Coding problems · System design studio
