Maximum Score Words Formed by Letters

Hard · Backtracking · Explanation and code example

Backtracking (Bit Mask)

How it works

Instead of recursive backtracking, we can iterate through all possible subsets using bit manipulation. With n words, there are 2^n possible subsets, each representable as an integer where bit i indicates whether word i is included. For each subset (bitmask), we check if all included words can be formed simultaneously and calculate the total score.

Steps

  1. Precompute frequency arrays and scores for all words.
  2. Iterate through all bitmasks from 0 to 2^n - 1:
    • For each bitmask, create a copy of the available letter counts.
    • For each bit set in the mask:
      • Check if the corresponding word can be formed with remaining letters.
      • If not, mark this subset as invalid and break.
      • If yes, subtract the word's letters and add its score.
    • If the subset is valid, update the maximum score.
  3. Return the maximum score found.

Complexity

  • Time complexity: O(m * n * 2 ^ n + N)
  • Space complexity: O(n + w)

Where n is the number of words, w is the maximum length of a word, m is the size of the array scores, and N is the size of the array letters.

Things to watch for

Not Restoring Letter Counts After Backtracking

When using backtracking, you must restore the letter counts after exploring the branch where you include a word. Forgetting to add the letters back after the recursive call means subsequent branches operate with incorrect letter availability, leading to wrong results or missing valid combinations.

Checking Word Validity Too Late

You should verify that a word can be formed with available letters before consuming those letters. If you subtract letters first and then discover the word is invalid, you've already corrupted the state. Always check availability first, then subtract if the word can be formed.

Counting Letters Incorrectly for Duplicate Characters

When a word contains duplicate characters (e.g., "aab"), you need the letter pool to have enough of each character. A common bug is checking if each character exists at least once, rather than checking if the count is sufficient. Use frequency arrays or counters that properly track multiple occurrences.

Confusing Word Score with Letter Score

The score array maps each letter to its value (index 0 = 'a', index 1 = 'b', etc.). A word's score is the sum of its letters' scores, not a single lookup. Misinterpreting this mapping or forgetting to sum all letters in the word produces incorrect scores.

Using Greedy Instead of Exhaustive Search

This problem requires exploring all 2^n subsets of words because including a high-scoring word might prevent including multiple other words that together score higher. Greedy approaches (e.g., always taking the highest-scoring valid word first) don't guarantee the optimal solution.

Python code example

from typing import List

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        letter_cnt = [0] * 26
        for c in letters:
            letter_cnt[ord(c) - ord('a')] += 1

        n = len(words)
        word_scores = [0] * n
        word_freqs = [[0] * 26 for _ in range(n)]

        for i, word in enumerate(words):
            for c in word:
                idx = ord(c) - ord('a')
                word_freqs[i][idx] += 1
                word_scores[i] += score[idx]

        res = 0

        for mask in range(1 << n):
            cur_score = 0
            cur_letter_cnt = letter_cnt[:]
            valid = True

            for i in range(n):
                if mask & (1 << i):
                    for j in range(26):
                        if word_freqs[i][j] > cur_letter_cnt[j]:
                            valid = False
                            break
                    if not valid:
                        break

                    for j in range(26):
                        cur_letter_cnt[j] -= word_freqs[i][j]

                    cur_score += word_scores[i]

            if valid:
                res = max(res, cur_score)

        return res

C++ code example

class Solution {
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> letterCnt(26, 0);
        for (char c : letters) {
            letterCnt[c - 'a']++;
        }

        int n = words.size();
        vector<int> wordScores(n, 0);
        vector<vector<int>> wordFreqs(n, vector<int>(26, 0));

        for (int i = 0; i < n; i++) {
            for (char c : words[i]) {
                int idx = c - 'a';
                wordFreqs[i][idx]++;
                wordScores[i] += score[idx];
            }
        }

        int res = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            int curScore = 0;
            vector<int> curLetterCnt = letterCnt;
            bool valid = true;

            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    for (int j = 0; j < 26; j++) {
                        if (wordFreqs[i][j] > curLetterCnt[j]) {
                            valid = false;
                            break;
                        }
                    }
                    if (!valid) break;

                    for (int j = 0; j < 26; j++) {
                        curLetterCnt[j] -= wordFreqs[i][j];
                    }

                    curScore += wordScores[i];
                }
            }

            if (valid) {
                res = max(res, curScore);
            }
        }

        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations