Maximum Score Words Formed by Letters — Problem & Solution
Maximum Score Words Formed by Letters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Maximum Score Words Formed by Letters is a hard coding problem on arrays, strings and backtracking, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Strings, Backtracking, Bitmask
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a list of words, a pool of letters (each entry is a single lowercase letter; letters may repeat) and an array score of length 26, where score[0] is the value of 'a', score[1] the value of 'b', and so on.
Choose any set of the words — each word at most once — that can be spelled together from the pool, where every letter tile is used at most once. The score of the set is the sum of the values of all letters in the chosen words.
Return the maximum score of any valid set (the empty set scores 0). You do not have to use every letter.
Example 1
Input: words = ["code","kairo","ode"], letters = ["c","o","d","e","k","a","i","r","o"], score = [1,0,3,2,1,0,0,0,1,0,5,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0]
Output: 16
Explanation: "code" (7) and "kairo" (9) use the two `o` tiles between them. "code" and "ode" would need two `d` tiles.
Example 2
Input: words = ["xyz"], letters = ["x","y"], score = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
Output: 0
Example 3
Input: words = ["aa","a"], letters = ["a","a","a"], score = [4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: 12
Constraints
1 <= words.length <= 141 <= words[i].length <= 151 <= letters.length <= 100letters[i].length == 1score.length == 260 <= score[i] <= 10words[i] and letters[i] contain only lowercase English letters
Hints for Maximum Score Words Formed by Letters
Hint 1
With at most 14 words there are at most 2^14 subsets — few enough to try them all.
Hint 2
Keep a count of the tiles still available; a word can be added only if the counts cover it.
Hint 3
Backtrack word by word: skip it, or (if it fits) subtract its letters, recurse, and add them back.
How to solve Maximum Score Words Formed by Letters
The word list is tiny, so search every subset by backtracking, carrying the remaining tile counts and pruning any branch that would overdraw a letter.
Approach
- Count the available tiles per letter and precompute each word's value.
dfs(i)returns the best score using wordsi..n-1: first try skipping wordi.- Then subtract word
i's letters from the counts; if no count went negative, tryvalue[i] + dfs(i + 1). - Restore the counts and return the better of the two options.
Why it works
Every subset of words corresponds to one root-to-leaf path of take/skip decisions, and a subset is valid exactly when no letter count ever goes negative along its path. So the recursion examines every valid subset and nothing else, and returns the largest score among them.
Complexity
- Time —
O(2^n · L), L = total word length - Space —
O(n + 26)
Pitfalls
- Restore the counts even when the word did not fit, since they were already decremented.
- A word may repeat a letter ("aa"), so it needs as many tiles as occurrences.
- Choosing words greedily by value fails — two medium words can beat one expensive word that blocks them.
Reference solution
Python
from typing import List
def maxScoreWords(words: List[str], letters: List[str], score: List[int]) -> int:
have = [0] * 26
for ch in letters:
have[ord(ch) - 97] += 1
codes = [[ord(ch) - 97 for ch in w] for w in words]
worth = [sum(score[c] for c in cs) for cs in codes]
n = len(words)
def dfs(i):
if i == n:
return 0
best = dfs(i + 1)
cs = codes[i]
for c in cs:
have[c] -= 1
if all(have[c] >= 0 for c in cs):
best = max(best, worth[i] + dfs(i + 1))
for c in cs:
have[c] += 1
return best
return dfs(0)Java
public static int maxScoreWords(String[] words, String[] letters, int[] score) {
int[] have = new int[26];
for (String l : letters) have[l.charAt(0) - 'a']++;
int n = words.length;
int[] worth = new int[n];
for (int i = 0; i < n; i++) {
for (int k = 0; k < words[i].length(); k++) worth[i] += score[words[i].charAt(k) - 'a'];
}
return mswDfs(words, worth, have, 0);
}
static int mswDfs(String[] words, int[] worth, int[] have, int i) {
if (i == words.length) return 0;
int best = mswDfs(words, worth, have, i + 1);
String w = words[i];
boolean ok = true;
for (int k = 0; k < w.length(); k++) have[w.charAt(k) - 'a']--;
for (int k = 0; k < w.length(); k++) if (have[w.charAt(k) - 'a'] < 0) ok = false;
if (ok) best = Math.max(best, worth[i] + mswDfs(words, worth, have, i + 1));
for (int k = 0; k < w.length(); k++) have[w.charAt(k) - 'a']++;
return best;
}C++
static int mswDfs(const vector<string>& words, const vector<int>& worth, vector<int>& have, int i) {
if (i == (int)words.size()) return 0;
int best = mswDfs(words, worth, have, i + 1);
const string& w = words[i];
bool ok = true;
for (char ch : w) have[ch - 'a']--;
for (char ch : w) if (have[ch - 'a'] < 0) ok = false;
if (ok) best = max(best, worth[i] + mswDfs(words, worth, have, i + 1));
for (char ch : w) have[ch - 'a']++;
return best;
}
int maxScoreWords(vector<string>& words, vector<string>& letters, vector<int>& score) {
vector<int> have(26, 0);
for (const string& l : letters) have[l[0] - 'a']++;
vector<int> worth(words.size(), 0);
for (size_t i = 0; i < words.size(); i++) {
for (char ch : words[i]) worth[i] += score[ch - 'a'];
}
return mswDfs(words, worth, have, 0);
}JavaScript
var maxScoreWords = function(words, letters, score) {
var have = new Array(26).fill(0);
for (var i = 0; i < letters.length; i++) have[letters[i].charCodeAt(0) - 97]++;
var codes = words.map(function(w) {
var cs = [];
for (var k = 0; k < w.length; k++) cs.push(w.charCodeAt(k) - 97);
return cs;
});
var worth = codes.map(function(cs) {
var s = 0;
for (var k = 0; k < cs.length; k++) s += score[cs[k]];
return s;
});
function dfs(i) {
if (i === words.length) return 0;
var best = dfs(i + 1);
var cs = codes[i], ok = true, k;
for (k = 0; k < cs.length; k++) have[cs[k]]--;
for (k = 0; k < cs.length; k++) if (have[cs[k]] < 0) ok = false;
if (ok) best = Math.max(best, worth[i] + dfs(i + 1));
for (k = 0; k < cs.length; k++) have[cs[k]]++;
return best;
}
return dfs(0);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.