#1255

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Score Words Formed by Letters

Calculate the highest total score by selecting words from a list using available letters, respecting individual letter scores and constraints.

array string dynamic programming backtracking bit manipulation

Problem Statement

You are given an array of strings representing words, an array of characters representing available letters (letters may appear multiple times), and an array of integers representing the score for each letter 'a' to 'z'. Your task is to select a subset of words such that each word can be formed using the available letters, with each letter used at most once, and maximize the total score.

Return the highest total score possible by forming valid words from the letters. Each word can only be used once, it is not necessary to use all letters, and the score of a word is the sum of its letters' assigned scores.

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

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

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

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.

Solution Approach

Precompute Letter Counts and Word Scores

Count the frequency of each letter in the available letters array and compute the score of each word based on individual letter scores. This allows constant-time checking of whether a word can be formed and quick calculation of incremental scores during recursion.

Backtracking with Subset Enumeration

Iterate over all subsets of words using recursion or bitmasking. For each subset, verify that all words can be formed with the remaining letters. If feasible, sum the scores and update the maximum score. This leverages the small input size (words.length <= 14) to explore 2^N combinations efficiently.

State Transition Dynamic Programming Optimization

Use a DP cache keyed by current letter availability or subset bitmask to avoid recalculating scores for previously encountered states. This ensures repeated states in the recursive exploration are skipped, significantly reducing unnecessary computations.

Complexity Analysis

Metric	Value
Time	O(2^W \cdot (L + A))
Space	O(A + W)

Time complexity is O(2^W * (L + A)) where W is the number of words, L is the maximum word length, and A is the alphabet size (26). Space complexity is O(A + W) to store letter counts and DP cache for state transitions.

What Interviewers Usually Probe

Look for state transition DP usage over naive backtracking.
Check how efficiently the candidate handles word feasibility checks using letter counts.
Observe if the candidate considers pruning invalid subsets to avoid redundant recursion.

Common Pitfalls or Variants

Common pitfalls

Attempting to generate all permutations of letters instead of word subsets, causing exponential blowup.
Failing to handle repeated letters correctly, leading to invalid word formation.
Not caching intermediate results, which results in unnecessary recomputation of subset scores.

Follow-up variants

Max score with repeated words allowed, adjusting DP accordingly.
Words have additional constraints like mandatory inclusion of specific letters.
Score function changes to include multipliers or penalties for certain letters.

FAQ

What is the main strategy for Maximum Score Words Formed by Letters?

Use backtracking with state transition dynamic programming to explore all valid word subsets efficiently.

Why is bitmasking useful in this problem?

Bitmasking allows representing subsets of words efficiently and is essential for DP caching of states during recursion.

How do I handle repeated letters in the letters array?

Precompute letter frequencies and decrement counts when a word uses letters; only proceed if all required letters are available.

What makes this problem suitable for state transition dynamic programming?

The small words.length lets you enumerate all subsets, and caching based on letter availability avoids recomputation, a classic DP state transition pattern.

Can all letters be used to maximize score?

Not necessarily; some letters may not contribute to high-scoring words. The goal is to maximize total score, not use all letters.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maxScoreWords(
        self, words: List[str], letters: List[str], score: List[int]
    ) -> int:
        cnt = Counter(letters)
        n = len(words)
        ans = 0
        for i in range(1 << n):
            cur = Counter(''.join([words[j] for j in range(n) if i >> j & 1]))
            if all(v <= cnt[c] for c, v in cur.items()):
                t = sum(v * score[ord(c) - ord('a')] for c, v in cur.items())
                ans = max(ans, t)
        return ans

Continue Practicing

#691 stickers to spell word #996 number of squareful arrays #943 find the shortest superstring