Watch 10 video solutions for Maximum Score Words Formed by Letters, a hard level problem involving Array, String, Dynamic Programming. This walkthrough by NeetCodeIO has 11,509 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Constraints:
1 <= words.length <= 141 <= words[i].length <= 151 <= letters.length <= 100letters[i].length == 1score.length == 260 <= score[i] <= 10words[i], letters[i] contains only lower case English letters.Problem Overview: You receive a list of words, a multiset of letters, and a score for each character. The task is to choose any subset of words such that the available letters can form them, maximizing the total score. Each letter can be used only as many times as it appears in the input.
Approach 1: Backtracking (Time: O(2^n * 26), Space: O(26 + n))
This approach explores every subset of words using recursion. For each word index, you decide whether to include the word or skip it. Maintain a frequency array for the remaining letters. When trying to include a word, decrement the corresponding character counts and verify that none go negative. If the word is valid, add its score and continue recursion. After the recursive call, restore the letter counts (backtrack). The key insight: the number of words is small (≤14), so exploring all subsets is feasible. Each validation step checks at most 26 characters. This technique relies heavily on backtracking and efficient frequency tracking with arrays. It’s straightforward, easy to implement, and performs well for the problem constraints.
Approach 2: Dynamic Programming with Bitmask (Time: O(2^n * 26), Space: O(2^n))
This method treats each subset of words as a bitmask. If there are n words, there are 2^n possible subsets. For each mask, compute the total character frequency of selected words and verify that it does not exceed the available letters. If valid, calculate the score using the provided character scores and update the maximum. Precomputing word frequencies reduces repeated work. Bit operations efficiently iterate through subsets, which is why this solution is commonly associated with bitmask enumeration and dynamic programming. Compared to backtracking, the logic is more iterative and predictable, though memory usage increases because all subset states are evaluated.
Recommended for interviews: The backtracking solution is usually expected. It demonstrates pruning, recursion control, and efficient state restoration. Interviewers want to see that you recognize the small constraint on the number of words and convert the problem into a subset exploration problem. The bitmask DP variant shows stronger familiarity with subset enumeration and state representation, which can be a good follow-up optimization or alternative discussion.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(2^n * 26) | O(26 + n) | Best for interviews and small word counts where recursive subset exploration with pruning is clear and efficient. |
| Dynamic Programming with Bitmask | O(2^n * 26) | O(2^n) | Useful when modeling subsets explicitly with bitmasks or when implementing an iterative subset DP solution. |