Maximum Score Words Formed by Letters: Backtracking with Letter Budgets

Given a list of words, a set of single letters (which may contain duplicates), and a score array where score[i] is the score of the i-th letter of the alphabet, find the maximum score you can achieve by forming any subset of words using the available letters. Each letter in letters can be used at most once, and each word in the subset must be fully spelled out.

This is LeetCode 1255: Maximum Score Words Formed by Letters, and it is a clean example of subset enumeration with a resource constraint. You are not just finding all subsets. You are finding the best subset that fits within a "letter budget." This pattern shows up whenever you need to pick the optimal combination of items subject to a shared pool of limited resources.

Why this problem matters

Most backtracking problems ask you to enumerate subsets, permutations, or combinations. This one adds a twist: you have a finite pool of letters, and each word you include in your subset "spends" from that pool. Two words might individually fit the budget, but together they might require more of a particular letter than you have.

This teaches you how to layer a feasibility check on top of the standard subset enumeration template. At each branch of the recursion tree, you ask: "If I include this word, do I still have enough letters?" If the answer is no, you skip that branch. If yes, you temporarily subtract the word's letters from the budget, recurse deeper, then restore the budget when you backtrack.

The constraint is frequency-based, not sum-based. Instead of checking whether a running total exceeds a target (like in Combination Sum), you compare an entire frequency array. That makes the feasibility check slightly more involved, but the backtracking skeleton is identical.

The approach

The key observation is that with at most 14 words (per the constraints), there are at most 2^14 = 16,384 possible subsets. That is small enough for brute-force enumeration. For each word at index i, you have two choices: include it or skip it. If you include it, subtract its letters from the available pool and add its score. If skipping, move on. At the end of the recursion, compare the accumulated score against the best seen so far.

The algorithm:

1. Count the frequency of each letter in letters.
2. For each word, precompute its letter frequency and total score.
3. Use backtracking to enumerate all subsets. At each word, try including it (if the letter budget allows) and try skipping it.
4. Track the maximum score across all valid subsets.

The solution

def maxScoreWords(words, letters, score):
    freq = [0] * 26
    for ch in letters:
        freq[ord(ch) - ord('a')] += 1

    def word_score(word):
        total = 0
        for ch in word:
            total += score[ord(ch) - ord('a')]
        return total

    def can_use(word, freq):
        count = [0] * 26
        for ch in word:
            idx = ord(ch) - ord('a')
            count[idx] += 1
            if count[idx] > freq[idx]:
                return False
        return True

    def use_word(word, freq, sign):
        for ch in word:
            freq[ord(ch) - ord('a')] += sign

    def backtrack(i):
        if i == len(words):
            return 0

        skip = backtrack(i + 1)

        include = 0
        if can_use(words[i], freq):
            use_word(words[i], freq, -1)
            include = word_score(words[i]) + backtrack(i + 1)
            use_word(words[i], freq, +1)

        return max(skip, include)

    return backtrack(0)

The function starts by building a frequency array from the available letters. For each recursive call at index i, it considers two branches: skip the current word entirely, or include it if the letter budget permits.

The can_use function checks whether every letter in the word is available in sufficient quantity. If it is, use_word with sign=-1 subtracts those letters from the pool before recursing, and use_word with sign=+1 restores them after. This is the classic choose-explore-unchoose pattern applied to a frequency array instead of a list.

The recursion returns the maximum score achievable from words at index i onward, given the current state of the letter budget.

Visual walkthrough

The walkthrough shows how the backtracking systematically tests each subset against the letter budget. Many subsets get rejected immediately because they need more of a specific letter than the pool provides. The valid subsets are scored, and the maximum is returned.

Complexity analysis

Time: There are 2^n possible subsets where n is the number of words. For each subset, the feasibility check and score computation scan through the letters of the included words. L is the maximum length of any single word. In the worst case, every subset is feasible and you compute scores for all of them.

Space: The recursion stack goes at most n levels deep (one level per word). The frequency array uses 26 entries. No additional data structures scale with the input size beyond that.

The building blocks

1. Frequency counting for letter budgets

The foundation of this problem is representing the available letters as a frequency array and checking whether a word fits within that budget:

freq = [0] * 26
for ch in letters:
    freq[ord(ch) - ord('a')] += 1

This same technique appears in anagram problems, ransom note, and any problem where you need to check character availability. The key insight is that comparing two frequency arrays is O(26), which is effectively constant time.

2. Subset enumeration with backtracking

The backtracking skeleton here is the same "include or skip" pattern from Subsets:

def backtrack(i):
    if i == len(items):
        return base_case

    skip = backtrack(i + 1)
    include = process(items[i]) + backtrack(i + 1)

    return best(skip, include)

The only addition is the feasibility check before the "include" branch. You guard the recursive call with can_use, and you wrap it in use_word / restore to manage the shared state. This is how you layer constraints onto the basic subset template without changing its structure.

Edge cases

Before submitting, check these:

• Empty words list: No words to choose from. The answer is 0.
• No letters available: letters is empty. No word can be formed. Answer is 0.
• Single word that fits: Only one word, and it fits the letter budget. The answer is that word's score.
• All words fit simultaneously: Every word can be spelled with the available letters at the same time. The answer is the sum of all word scores.
• Duplicate letters in a word: A word like "dad" needs two d's. Make sure your frequency check accounts for repeated characters within a single word.
• Words with zero-score letters: A word might technically be formable but contribute very little score. Including it wastes letters that could be used for higher-scoring words.

From understanding to recall

You see the pattern: enumerate subsets, check a frequency-based constraint, track the maximum score. The backtracking skeleton is identical to Subsets, with a feasibility guard layered on top. But under interview pressure, the details matter. Building the frequency array, writing the can_use check, managing the choose-restore cycle on the frequency array instead of a simple list. These are the pieces that trip people up.

Spaced repetition locks in the details. You practice writing the frequency check and the backtracking loop from memory until they are automatic. After a few rounds, you stop thinking about off-by-one errors in the ord conversion or forgetting to restore the frequency array after backtracking. The code just flows.

Related posts

• Subsets - The foundational subset enumeration pattern
• Combination Sum - Backtracking with constraints on element reuse
• Word Search - Backtracking on a grid with character matching

CodeBricks breaks Maximum Score Words into its frequency-counting and subset-enumeration building blocks, then drills them independently with spaced repetition. You type the backtracking skeleton and the letter budget check from scratch until they are automatic. When a constrained subset problem shows up in your interview, you do not hesitate. You just write it.