Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1255. Maximum Score Words Formed by Letters - Leetcode Solution

Code Implementation

from collections import Counter

class Solution:
    def maxScoreWords(self, words, letters, score):
        letter_count = Counter(letters)
        n = len(words)
        word_counts = [Counter(word) for word in words]
        word_scores = [sum(score[ord(c)-ord('a')]*cnt for c, cnt in wc.items()) for wc in word_counts]
        self.ans = 0

        def backtrack(i, curr_score, curr_count):
            if i == n:
                self.ans = max(self.ans, curr_score)
                return
            # Try to skip the current word
            backtrack(i+1, curr_score, curr_count)
            # Try to use the current word if possible
            can_use = True
            for c in word_counts[i]:
                if curr_count[c] < word_counts[i][c]:
                    can_use = False
                    break
            if can_use:
                for c in word_counts[i]:
                    curr_count[c] -= word_counts[i][c]
                backtrack(i+1, curr_score + word_scores[i], curr_count)
                for c in word_counts[i]:
                    curr_count[c] += word_counts[i][c]

        backtrack(0, 0, letter_count.copy())
        return self.ans
      
class Solution {
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> letterCount(26, 0);
        for (char c : letters) letterCount[c - 'a']++;
        int n = words.size();
        int ans = 0;

        function<void(int, int, vector<int>&)> backtrack = [&](int i, int currScore, vector<int>& currCount) {
            if (i == n) {
                ans = max(ans, currScore);
                return;
            }
            // Skip current word
            backtrack(i + 1, currScore, currCount);
            // Try to use current word
            vector<int> wordCount(26, 0);
            for (char c : words[i]) wordCount[c - 'a']++;
            bool canUse = true;
            for (int c = 0; c < 26; ++c) {
                if (wordCount[c] > currCount[c]) {
                    canUse = false;
                    break;
                }
            }
            if (canUse) {
                for (int c = 0; c < 26; ++c) currCount[c] -= wordCount[c];
                int wordScore = 0;
                for (int c = 0; c < 26; ++c) wordScore += wordCount[c] * score[c];
                backtrack(i + 1, currScore + wordScore, currCount);
                for (int c = 0; c < 26; ++c) currCount[c] += wordCount[c];
            }
        };

        backtrack(0, 0, letterCount);
        return ans;
    }
};
      
class Solution {
    int ans = 0;

    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        int[] letterCount = new int[26];
        for (char c : letters) letterCount[c - 'a']++;
        backtrack(words, score, letterCount, 0, 0);
        return ans;
    }

    private void backtrack(String[] words, int[] score, int[] currCount, int i, int currScore) {
        if (i == words.length) {
            ans = Math.max(ans, currScore);
            return;
        }
        // Skip current word
        backtrack(words, score, currCount, i + 1, currScore);
        // Try to use current word
        int[] wordCount = new int[26];
        for (char c : words[i].toCharArray()) wordCount[c - 'a']++;
        boolean canUse = true;
        for (int c = 0; c < 26; ++c) {
            if (wordCount[c] > currCount[c]) {
                canUse = false;
                break;
            }
        }
        if (canUse) {
            for (int c = 0; c < 26; ++c) currCount[c] -= wordCount[c];
            int wordScore = 0;
            for (int c = 0; c < 26; ++c) wordScore += wordCount[c] * score[c];
            backtrack(words, score, currCount, i + 1, currScore + wordScore);
            for (int c = 0; c < 26; ++c) currCount[c] += wordCount[c];
        }
    }
}
      
var maxScoreWords = function(words, letters, score) {
    let letterCount = Array(26).fill(0);
    for (let c of letters) letterCount[c.charCodeAt(0) - 97]++;
    let n = words.length;
    let ans = 0;

    function backtrack(i, currScore, currCount) {
        if (i === n) {
            ans = Math.max(ans, currScore);
            return;
        }
        // Skip current word
        backtrack(i + 1, currScore, currCount);
        // Try to use current word
        let wordCount = Array(26).fill(0);
        for (let c of words[i]) wordCount[c.charCodeAt(0) - 97]++;
        let canUse = true;
        for (let c = 0; c < 26; ++c) {
            if (wordCount[c] > currCount[c]) {
                canUse = false;
                break;
            }
        }
        if (canUse) {
            for (let c = 0; c < 26; ++c) currCount[c] -= wordCount[c];
            let wordScore = 0;
            for (let c = 0; c < 26; ++c) wordScore += wordCount[c] * score[c];
            backtrack(i + 1, currScore + wordScore, currCount);
            for (let c = 0; c < 26; ++c) currCount[c] += wordCount[c];
        }
    }

    backtrack(0, 0, letterCount.slice());
    return ans;
};

Problem Description

Given a list of words words, a list of available letters letters, and a list of scores score where score[i] is the score for the i-th letter of the alphabet, your task is to find the maximum score you can get by selecting a subset of words and forming them using the letters in letters (each letter can be used at most once). The score for each word is the sum of scores for each letter in the word. You cannot reuse letters across words, and you can use each word at most once.

Thought Process

At first glance, this problem looks similar to the classic knapsack problem: we have a set of items (words) with associated values (scores), and a limited resource (letters). The brute-force approach would be to try all possible subsets of words, check if each can be formed from the available letters, and compute the total score for each valid subset, keeping track of the maximum. However, as the number of words grows, the number of subsets grows exponentially, making brute-force infeasible for large inputs. To optimize, we need a way to efficiently check the validity of each subset and avoid redundant calculations.

Solution Approach

The solution uses backtracking to explore all possible combinations of words, but prunes invalid choices early. Here is the step-by-step approach:
  • Count the available letters using a frequency array or hash map for quick lookups.
  • For each word, precompute its letter frequency and total score to avoid recomputation.
  • Define a recursive backtracking function that, for each word, decides whether to include it or not:
    • If the current word can be formed with the available letters, try both including and excluding it.
    • When including a word, subtract its letter counts from the available letters, add its score to the current total, and recurse to the next word.
    • When excluding, simply recurse to the next word.
    • After recursion, restore the letter counts (backtrack) to try other combinations.
  • Keep track of the maximum score found during this process.
  • This approach ensures that all valid subsets are considered, but avoids unnecessary work by pruning branches where it's impossible to form the word with remaining letters.

Example Walkthrough

Suppose words = ["dog", "cat", "dad", "good"], letters = ["a","a","c","d","d","g","o","o"], and score assigns 1 to all letters for simplicity.
  • First, count available letters: a:2, c:1, d:2, g:1, o:2.
  • Try all combinations:
    • ["dog"]: can be formed (d,o,g), uses 1 d, 1 o, 1 g.
    • ["cat"]: can be formed (c,a,t) but t is missing, so skip.
    • ["dad"]: can be formed (d,a,d), uses 2 d, 1 a.
    • ["good"]: can be formed (g,o,o,d), uses 1 g, 2 o, 1 d.
  • Try combinations like ["dog", "dad"]: after using "dog", only 1 d and 1 a left, but "dad" needs 2 d, so invalid.
  • Try ["dad", "good"]: after using "dad", 0 d left, but "good" needs 1 d, so invalid.
  • The best valid combination is ["dog", "dad"] or ["good"], depending on scores; the backtracking process checks all possibilities and keeps the best score.

Time and Space Complexity

  • Brute-force: There are 2^n possible subsets of words, and for each subset, checking validity takes O(L) time where L is the total length of all words. So overall time is O(2^n * L).
  • Optimized backtracking: Still explores up to 2^n subsets, but prunes invalid branches early, often reducing actual work. Each branch checks letter counts and scores in O(W) time, where W is the length of the current word.
  • Space complexity: O(n + 26) for word counts and letter frequencies, plus recursion stack of depth n.

Summary

The problem is a variation of the subset/knapsack problem with the twist of letter constraints. The elegant solution uses backtracking to explore all subsets, pruning branches that cannot form valid words with the available letters. Precomputing word scores and letter frequencies speeds up checks, and restoring state after recursion (backtracking) allows for efficient exploration of all combinations. This approach is both simple and effective for the problem's constraints.