Skip to main content
Talentd

Maximum Score Words Formed by Letters - Solution & Explanation

HardArrayStringDynamic ProgrammingBacktracking18 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

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 <= 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.

Approach Overview

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 1: Approach 1: Backtracking

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Dynamic Programming

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.

Code

C++Python

C++

Python

Complexity

Time Complexity: O(n * 2^n), where n is the number of words.
Space Complexity: O(2^n) for the DP map.

Try this approach in the editor →

Approach 3: Binary Enumeration

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n), where n is the depth of the recursion stack.

Approach 2: Dynamic Programming

Time Complexity: O(n * 2^n), where n is the number of words.
Space Complexity: O(2^n) for the DP map.

Binary Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BacktrackingO(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 BitmaskO(2^n * 26)O(2^n)Useful when modeling subsets explicitly with bitmasks or when implementing an iterative subset DP solution.

Video Solution

Maximum Score Words Formed By Letters - Leetcode 1255 - Python • NeetCodeIO • 11,697 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Score Words Formed by Letters easy or hard?
The problem is labeled Hard because it combines subset enumeration, scoring logic, and constraint validation. The underlying idea is manageable once you recognize that the number of words is small, making backtracking or bitmask enumeration feasible.
How to solve Maximum Score Words Formed by Letters in O(n)?
An O(n) solution is not possible because the problem requires evaluating combinations of words. The optimal solutions examine subsets of the word list, leading to O(2^n) complexity. Efficient implementations reduce constant factors using frequency arrays and pruning invalid branches early.
What is the best approach for Maximum Score Words Formed by Letters?
Backtracking is the most practical approach. The algorithm recursively decides whether to include or skip each word while tracking remaining letter frequencies. Since the number of words is small (up to 14), exploring all subsets with pruning works efficiently with time complexity O(2^n * 26).
What data structure is used in Maximum Score Words Formed by Letters?
The core data structures are frequency arrays for tracking character counts and recursion stacks for exploring subsets. Some implementations also use bitmasks to represent subsets of words efficiently in dynamic programming solutions.
What is the time complexity of Maximum Score Words Formed by Letters?
Both common solutions run in O(2^n * 26) time, where n is the number of words. Each subset of words is evaluated, and character frequency checks take up to 26 operations. Space complexity is O(26 + n) for backtracking and O(2^n) for the bitmask DP approach.
Maximum Score Words Formed by Letters Python or Java solution approach?
Python and Java implementations typically use recursive backtracking with an integer array of size 26 to store letter counts. Each recursive step attempts to include the current word, updates the counts, computes the score, and backtracks after exploring the branch.
Is Maximum Score Words Formed by Letters asked at Google, Amazon, or Meta?
Subset search and backtracking problems similar to this one appear in interviews at companies like Google, Amazon, and Meta. The question tests recursive exploration, pruning invalid states, and efficient use of frequency arrays for constraint checking.

Ready to solve this problem?

Practice Maximum Score Words Formed by Letters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Good People Based on Statements