Maximum Score Words Formed by Letters
Problem
Given a list of words, a multiset of available letters, and a score array (score[0] for 'a' … score[25] for 'z'), return the maximum total score of any valid subset of words. A word can be used at most once, and the letters used across all chosen words cannot exceed the available supply.
words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]23def maxScoreWords(words, letters, score):
avail = [0] * 26
for c in letters:
avail[ord(c) - 97] += 1
def dfs(i, supply):
if i == len(words):
return 0
best = dfs(i + 1, supply) # skip word i
gain, ok = 0, True
for c in words[i]: # try to take word i
j = ord(c) - 97
supply[j] -= 1
gain += score[j]
if supply[j] < 0:
ok = False
if ok:
best = max(best, gain + dfs(i + 1, supply))
for c in words[i]: # undo
supply[ord(c) - 97] += 1
return best
return dfs(0, avail)function maxScoreWords(words, letters, score) {
const avail = new Array(26).fill(0);
for (const c of letters) avail[c.charCodeAt(0) - 97]++;
function dfs(i, supply) {
if (i === words.length) return 0;
let best = dfs(i + 1, supply); // skip word i
let gain = 0, ok = true;
for (const c of words[i]) { // try to take word i
const j = c.charCodeAt(0) - 97;
supply[j]--; gain += score[j];
if (supply[j] < 0) ok = false;
}
if (ok) best = Math.max(best, gain + dfs(i + 1, supply));
for (const c of words[i]) supply[c.charCodeAt(0) - 97]++; // undo
return best;
}
return dfs(0, avail);
}class Solution {
public int maxScoreWords(String[] words, char[] letters, int[] score) {
int[] avail = new int[26];
for (char c : letters) avail[c - 'a']++;
return dfs(words, 0, avail, score);
}
private int dfs(String[] words, int i, int[] supply, int[] score) {
if (i == words.length) return 0;
int best = dfs(words, i + 1, supply, score); // skip word i
int gain = 0; boolean ok = true;
for (char c : words[i].toCharArray()) { // try to take word i
int j = c - 'a';
supply[j]--; gain += score[j];
if (supply[j] < 0) ok = false;
}
if (ok) best = Math.max(best, gain + dfs(words, i + 1, supply, score));
for (char c : words[i].toCharArray()) supply[c - 'a']++; // undo
return best;
}
}class Solution {
public:
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
vector<int> avail(26, 0);
for (char c : letters) avail[c - 'a']++;
return dfs(words, 0, avail, score);
}
int dfs(vector<string>& words, int i, vector<int>& supply, vector<int>& score) {
if (i == (int)words.size()) return 0;
int best = dfs(words, i + 1, supply, score); // skip word i
int gain = 0; bool ok = true;
for (char c : words[i]) { // try to take word i
int j = c - 'a';
supply[j]--; gain += score[j];
if (supply[j] < 0) ok = false;
}
if (ok) best = max(best, gain + dfs(words, i + 1, supply, score));
for (char c : words[i]) supply[c - 'a']++; // undo
return best;
}
};Explanation
For each word we face a simple yes/no choice: take it or skip it. Taking a word earns its letter score but uses up letters from a shared supply. The goal is to pick the subset that maximizes total score without running out of any letter.
We first build avail[26], the count of each available letter. Then dfs(i, supply) decides about word i. It computes the best you can get by skipping it, then tries taking it: subtract its letters from supply and add its gain.
Taking is only allowed if no letter count goes below zero (the ok flag). If valid, we compare gain + dfs(i + 1, supply) against the skip option and keep the larger. Crucially, after the recursive call we undo the letter changes so the next branch starts clean — that is the backtracking step.
Example: with letters for "dad" and "good" available, taking both scores 11 + 12 = 23. Once those letters are spent you cannot also afford "dog" or "cat", so 23 is the maximum.
Because every word's take/skip branch is explored and undone, the search covers all valid subsets and returns the best score.