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.
This approach uses backtracking to explore all possible subsets of the list of words. For each possible subset, we calculate the score by adding scores of words whose characters can be covered by the given letters. The final solution is the maximum score achievable from all possible combinations.
This C implementation uses a recursive backtracking approach. Beginning with the first word, it decides whether to include the word in the count by checking the frequency available in the letters. If a word is included, its letter usage is deducted from the availability. The recursion continues to explore further possibilities. Finally, the maximum score is recorded.
Time Complexity: O(2^n), where n is the number of words. This is because we're considering every possible subset of the set of words.
Space Complexity: O(n), where n is the depth of the recursion stack.
In this approach, we use dynamic programming to calculate the maximum score. A common dynamic programming technique involves using a bitmask to represent the set of words included in the current set, allowing us to avoid recalculating results for previously solved subproblems.
In this C++ solution, we use bitmask dynamic programming to keep track of which words are included in the word set. Each possible word subset is a potential solution, and we calculate its score by checking if it can be formed given the available letters and scoring accordingly.
Time Complexity: O(n * 2^n), where n is the number of words.
Space Complexity: O(2^n) for the DP map.
Given the small data range in the problem, we can use binary enumeration to enumerate all word combinations for the given word list. Then, we check whether each word combination meets the requirements of the problem. If it does, we calculate its score and finally take the word combination with the highest score.
First, we use a hash table or array cnt to record the number of occurrences of each letter in the alphabet letters.
Next, we use binary enumeration to enumerate all word combinations. Each bit in the binary represents whether each word in the word list is selected. If the ith bit is 1, it means the ith word is selected; otherwise, the ith word is not selected.
Then, we count the number of occurrences of each letter in the current word combination and record it in the hash table or array cur. If the number of occurrences of each letter in cur is not greater than the corresponding letter in cnt, it means the current word combination meets the requirements of the problem. We calculate the score of the current word combination and take the word combination with the highest score.
The time complexity is (2^n times n times M), and the space complexity is O(C). Where n and M are the number of words in the word set and the maximum length of the word, respectively; and C is the number of letters in the alphabet, in this problem, C=26.
| Approach | Complexity |
|---|---|
| Approach 1: Backtracking | Time Complexity: O(2^n), where n is the number of words. This is because we're considering every possible subset of the set of words. |
| Approach 2: Dynamic Programming | Time Complexity: O(n * 2^n), where n is the number of words. |
| Binary Enumeration | — |
| 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. |
Maximum Score Words Formed By Letters - Leetcode 1255 - Python • NeetCodeIO • 11,509 views views
Watch 9 more video solutions →Practice Maximum Score Words Formed by Letters with our built-in code editor and test cases.
Practice on FleetCode