⚡Flashcard Drill➔
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

  1. Pre-filter the words that cannot be formed at all, and precompute each word's letter counts and score.
  2. Backtrack over the filtered words, maintaining a count of the letters used.
  3. A word can be added only if the remaining letters suffice.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Backtracking Problems