NeetCode #520LC-1255HardBacktracking
← Back to All Problems#520 · #1255 · Maximum Score Words Formed by Letters(得分最高的单词集合)
📌 Problem Statement & Constraints
You are given
words, letters (available letters, each usable once) and score (the score of each letter a-z). Return the maximum score of any set of words formed from the letters. Constraints: 1 <= words.length <= 14, 1 <= words[i].length, letters.length <= 15.💡 Core Algorithmic Approaches
- Pre-filter the words that cannot be formed at all, and precompute each word's letter counts and score.
- Backtrack over the filtered words, maintaining a count of the letters used.
- A word can be added only if the remaining letters suffice.
- Track the best total at every node, since any prefix of the selection is a valid answer.
💻 Benchmark Python3 Implementation
class Solution:
def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
from collections import Counter
avail = Counter(letters)
# keep only feasible words, with their letter counts and scores
opts = []
for w in words:
c = Counter(w)
if all(c[ch] <= avail[ch] for ch in c):
opts.append((c, sum(score[ord(ch) - 97] * cnt for ch, cnt in c.items())))
self.best = 0
def dfs(i: int, used: Counter, total: int) -> None:
self.best = max(self.best, total)
for j in range(i, len(opts)):
c, s = opts[j]
if all(used[ch] + c[ch] <= avail[ch] for ch in c):
for ch in c:
used[ch] += c[ch]
dfs(j + 1, used, total + s)
for ch in c: # backtrack
used[ch] -= c[ch]
dfs(0, Counter(), 0)
return self.best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(2^k * L) where k is the number of feasible words and L the average word length.
💾 Space Complexity
O(26) for the counters plus O(k) recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Not pre-filtering infeasible words: they would be tried at every node for no benefit.
- Forgetting the
used[ch]accumulation: the same letter cannot be reused across words. - Updating the best only at the leaves: every partial selection is a candidate.
- Recomputing a word's score inside the recursion: precomputing it once per word is much faster.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.