Maximum Score Words Formed by Letters solution and explanation
Google
9 more videos on this problem
Maximum Score Words Formed By Letters - Leetcode 1255 - PythonNeetCodeIO · 14:10 · 11K views
Maximum Score Words Formed by Letters | Why Backtracking | Why Greedy Fails | Leetcode 1255codestorywithMIK · 30:12 · 10K views
1255. Maximum Score Words Formed by Letters | Backtracking | Bit Manipulation | RecursionAryan Mittal · 25:38 · 3K views
1255. Maximum Score Words Formed by Letters | LEETCODE HARD | LEETCODE | BIT MANIPILATIONcode Explainer · 10:58 · 3K views
LeetCode 1255. Maximum Score Words Formed by LettersHappy Coding · 23:31 · 1K views
Leetcode 1255: Maximum Score Words Formed by LettersAlgorithms Casts · 34:40 · 1K views
Maximum Score Words Formed by Letters (LeetCode 1255) (Hard (Recursion,Backtracking, Subsets)CodeWithARB · 51:03 · 366 views
LeetCode 1255. Maximum Score Words Formed by LettersIsaac Ho · 2:19 · 239 views
LeetCode 1255 - Maximum Score Words Formed By Letters - JavaAlpha-Code · 20:43 · 124 views
Maximum Score Words Formed by Letters | LeetCode: 1255 | Backtracking | LeetCode HardAmit Dhyani · 22:13 · 105 views
The problem
Given a list of words, list of single letters (might be repeating) and score of every character.
Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times).
It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', ... ,'z' is given by score[0], score[1], ... , score[25] respectively.
Example 1:
Input: 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] Output: 23 Explanation: Score a=1, c=9, d=5, g=3, o=2 Given letters, we can form the words "dad" (5+1+5) and "good" (3+2+2+5) with a score of 23. Words "dad" and "dog" only get a score of 21.
Example 2:
Input: words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10] Output: 27 Explanation: Score a=4, b=4, c=4, x=5, z=10 Given letters, we can form the words "ax" (4+5), "bx" (4+5) and "cx" (4+5) with a score of 27. Word "xxxz" only get a score of 25.
Example 3:
Input: words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0] Output: 0 Explanation: Letter "e" can only be used once.
Constraints:
1 <= words.length <= 141 <= words[i].length <= 151 <= letters.length <= 100letters[i].length == 1score.length == 260 <= score[i] <= 10words[i],letters[i]contains only lower case English letters.
Approach overview
Problem Overview: You receive a list of words, a multiset of letters, and a score for each character. The task is to choose any subset of words such that the available letters can form them, maximizing the total score. Each letter can be used only as many times as it appears in the input.
Approach 1: Backtracking (Time: O(2^n * 26), Space: O(26 + n))
This approach explores every subset of words using recursion. For each word index, you decide whether to include the word or skip it. Maintain a frequency array for the remaining letters. When trying to include a word, decrement the corresponding character counts and verify that none go negative. If the word is valid, add its score and continue recursion. After the recursive call, restore the letter counts (backtrack). The key insight: the number of words is small (≤14), so exploring all subsets is feasible. Each validation step checks at most 26 characters. This technique relies heavily on backtracking and efficient frequency tracking with arrays. It’s straightforward, easy to implement, and performs well for the problem constraints.
Approach 2: Dynamic Programming with Bitmask (Time: O(2^n * 26), Space: O(2^n))
This method treats each subset of words as a bitmask. If there are n words, there are 2^n possible subsets. For each mask, compute the total character frequency of selected words and verify that it does not exceed the available letters. If valid, calculate the score using the provided character scores and update the maximum. Precomputing word frequencies reduces repeated work. Bit operations efficiently iterate through subsets, which is why this solution is commonly associated with bitmask enumeration and dynamic programming. Compared to backtracking, the logic is more iterative and predictable, though memory usage increases because all subset states are evaluated.
Recommended for interviews: The backtracking solution is usually expected. It demonstrates pruning, recursion control, and efficient state restoration. Interviewers want to see that you recognize the small constraint on the number of words and convert the problem into a subset exploration problem. The bitmask DP variant shows stronger familiarity with subset enumeration and state representation, which can be a good follow-up optimization or alternative discussion.
Approach 1: Approach 1: Backtracking
This approach uses backtracking to explore all possible subsets of the list of words. For each possible subset, we calculate the score by adding scores of words whose characters can be covered by the given letters. The final solution is the maximum score achievable from all possible combinations.
from typing import List
class Solution:
def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
from collections import Counter
freq = Counter(letters)
def backtrack(index):
if index == len(words):
return 0
skip = backtrack(index + 1)
word_score, can_form = 0, True
word_count = Counter(words[index])
for char, count in word_count.items():
if freq[char] < count:
can_form = False
break
word_score += score[ord(char) - ord('a')] * count
use = 0
if can_form:
for char, count in word_count.items():
freq[char] -= count
use = word_score + backtrack(index + 1)
for char, count in word_count.items():
freq[char] += count
return max(skip, use)
return backtrack(0)import java.util.List;
class Solution {
public int maxScoreWords(String[] words, char[] letters, int[] score) {
int[] letterCount = new int[26];
for (char letter : letters) {
letterCount[letter - 'a']++;
}
return backtrack(words, letterCount, score, 0);
}
private int backtrack(String[] words, int[] letterCount, int[] score, int index) {
if (index == words.length) return 0;
int skip = backtrack(words, letterCount, score, index + 1);
int wordScore = 0;
int[] tempCount = new int[26];
boolean canForm = true;
for (char c : words[index].toCharArray()) {
if (++tempCount[c - 'a'] > letterCount[c - 'a']) {
canForm = false;
break;
}
wordScore += score[c - 'a'];
}
int use = 0;
if (canForm) {
for (char c : words[index].toCharArray()) letterCount[c - 'a'] -= tempCount[c - 'a'];
use = wordScore + backtrack(words, letterCount, score, index + 1);
for (char c : words[index].toCharArray()) letterCount[c - 'a'] += tempCount[c - 'a'];
}
return Math.max(skip, use);
}
}#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
vector<int> letterCount(26, 0);
for (char letter : letters)
letterCount[letter - 'a']++;
return backtrack(words, letterCount, score, 0);
}
int backtrack(vector<string>& words, vector<int>& letterCount, vector<int>& score, int index) {
if (index == words.size()) return 0;
int skip = backtrack(words, letterCount, score, index + 1);
int wordScore = 0;
vector<int> tempCount(26);
bool canForm = true;
for (char c : words[index]) {
if (++tempCount[c - 'a'] > letterCount[c - 'a']) {
canForm = false;
break;
}
wordScore += score[c - 'a'];
}
int use = 0;
if (canForm) {
for (char c : words[index]) letterCount[c - 'a'] -= tempCount[c - 'a'];
use = wordScore + backtrack(words, letterCount, score, index + 1);
for (char c : words[index]) letterCount[c - 'a'] += tempCount[c - 'a'];
}
return max(skip, use);
}
};var maxScoreWords = function(words, letters, score) {
let freq = Array(26).fill(0);
for (let letter of letters) {
freq[letter.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
const backtrack = (index) => {
if (index === words.length) return 0;
let skip = backtrack(index + 1);
let wordScore = 0;
let canForm = true;
let wordFreq = Array(26).fill(0);
for (let char of words[index]) {
wordFreq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
if (wordFreq[char.charCodeAt(0) - 'a'.charCodeAt(0)] > freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]) {
canForm = false;
break;
}
wordScore += score[char.charCodeAt(0) - 'a'.charCodeAt(0)];
}
let use = 0;
if (canForm) {
for (let char of words[index]) {
freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]--;
}
use = wordScore + backtrack(index + 1);
for (let char of words[index]) {
freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
}
return Math.max(skip, use);
}
return backtrack(0);
};#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int calculateScore(char* word, int* score) {
int sum = 0;
for (int i = 0; word[i] != '\0'; i++) {
sum += score[word[i] - 'a'];
}
return sum;
}
void backTrack(char** words, int wordsSize, int* letterCount, int* score, int currentScore, int* maxScore, int index) {
if (index == wordsSize) {
if (currentScore > *maxScore) *maxScore = currentScore;
return;
}
backTrack(words, wordsSize, letterCount, score, currentScore, maxScore, index + 1);
int canUseWord = 1;
char* word = words[index];
for (int i = 0; word[i] != '\0'; i++) {
if (letterCount[word[i] - 'a'] <= 0) {
canUseWord = 0;
break;
}
letterCount[word[i] - 'a']--;
}
if (canUseWord) {
backTrack(words, wordsSize, letterCount, score, currentScore + calculateScore(word, score), maxScore, index + 1);
}
for (int i = 0; word[i] != '\0'; i++) {
letterCount[word[i] - 'a']++;
}
}
int maxScoreWords(char** words, int wordsSize, char* letters, int lettersSize, int* score) {
int letterCount[26] = {0};
for (int i = 0; i < lettersSize; i++) {
letterCount[letters[i] - 'a']++;
}
int maxScore = 0;
backTrack(words, wordsSize, letterCount, score, 0, &maxScore, 0);
return maxScore;
}using System;
using System.Collections.Generic;
public class Solution {
public int MaxScoreWords(string[] words, char[] letters, int[] score) {
Dictionary<char, int> freq = new Dictionary<char, int>();
foreach (var letter in letters) {
if (freq.ContainsKey(letter)) freq[letter]++;
else freq[letter] = 1;
}
return Backtrack(words, freq, score, 0);
}
private int Backtrack(string[] words, Dictionary<char, int> freq, int[] score, int index) {
if (index == words.Length) return 0;
int skip = Backtrack(words, freq, score, index + 1);
int wordScore = 0;
bool canForm = true;
var tempFreq = new Dictionary<char, int>();
foreach (var c in words[index]) {
if (!tempFreq.ContainsKey(c)) tempFreq[c] = 0;
tempFreq[c]++;
if (!freq.ContainsKey(c) || tempFreq[c] > freq[c]) {
canForm = false;
break;
}
wordScore += score[c - 'a'];
}
int use = 0;
if (canForm) {
foreach (var c in words[index]) freq[c]--;
use = wordScore + Backtrack(words, freq, score, index + 1);
foreach (var c in words[index]) freq[c]++;
}
return Math.Max(skip, use);
}
}In this Python solution, we make use of the Counter class to manage the frequency of letters. The backtrack function increments and decrements these counts depending on whether the current word is added for scoring. It recursively finds the best score outcome.
Time Complexity: O(2^n).
Space Complexity: O(n).
Approach 2: Approach 2: Dynamic Programming
In this approach, we use dynamic programming to calculate the maximum score. A common dynamic programming technique involves using a bitmask to represent the set of words included in the current set, allowing us to avoid recalculating results for previously solved subproblems.
from typing import List
class Solution:
def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
from collections import Counter
freq = Counter(letters)
n = len(words)
dp = [-1] * (1 << n)
def getWordScore(word):
return sum([score[ord(c) - ord('a')] for c in word])
def canForm(word):
counter = Counter(word)
for c in counter:
if counter[c] > freq[c]:
return False
return True
def dpMask(mask):
if dp[mask] != -1:
return dp[mask]
maxScore = 0
for i in range(n):
if not (mask & (1 << i)) and canForm(words[i]):
new_score = getWordScore(words[i])
maxScore = max(maxScore, new_score + dpMask(mask | (1 << i)))
dp[mask] = maxScore
return maxScore
return dpMask(0)#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
vector<int> letterCount(26, 0);
for (char letter : letters)
letterCount[letter - 'a']++;
int n = words.size();
return dp(words, letterCount, score, 0, n);
}
private:
unordered_map<int, int> dpMap;
int dp(vector<string>& words, vector<int>& letterCount, vector<int>& score, int mask, int n) {
if (dpMap.count(mask)) return dpMap[mask];
int maxScore = 0;
for (int i = 0; i < n; ++i) {
if (!(mask & (1 << i))) {
int currScore = 0;
bool valid = true;
vector<int> lCount = letterCount;
for (char c : words[i]) {
if (--lCount[c - 'a'] < 0) {
valid = false;
break;
}
currScore += score[c - 'a'];
}
if (valid) {
maxScore = max(maxScore, currScore + dp(words, lCount, score, mask | (1 << i), n));
}
}
}
return dpMap[mask] = maxScore;
}
};The Python solution employs a DP array to handle subsets of words, calculating each subset's score efficiently by storing previously-calculated results. We compute a score using bitmasks to include/exclude each word.
Time Complexity: O(n * 2^n).
Space Complexity: O(2^n) for DP results.
Approach 3: Binary Enumeration
Given the small data range in the problem, we can use binary enumeration to enumerate all word combinations for the given word list. Then, we check whether each word combination meets the requirements of the problem. If it does, we calculate its score and finally take the word combination with the highest score.
First, we use a hash table or array cnt to record the number of occurrences of each letter in the alphabet letters.
Next, we use binary enumeration to enumerate all word combinations. Each bit in the binary represents whether each word in the word list is selected. If the ith bit is 1, it means the ith word is selected; otherwise, the ith word is not selected.
Then, we count the number of occurrences of each letter in the current word combination and record it in the hash table or array cur. If the number of occurrences of each letter in cur is not greater than the corresponding letter in cnt, it means the current word combination meets the requirements of the problem. We calculate the score of the current word combination and take the word combination with the highest score.
The time complexity is (2^n times n times M), and the space complexity is O(C). Where n and M are the number of words in the word set and the maximum length of the word, respectively; and C is the number of letters in the alphabet, in this problem, C=26.
func maxScoreWords(words []string, letters []byte, score []int) (ans int) {
cnt := [26]int{}
for _, c := range letters {
cnt[c-'a']++
}
n := len(words)
for i := 0; i < 1<<n; i++ {
cur := [26]int{}
for j := 0; j < n; j++ {
if i>>j&1 == 1 {
for _, c := range words[j] {
cur[c-'a']++
}
}
}
ok := true
t := 0
for i, v := range cur {
if v > cnt[i] {
ok = false
break
}
t += v * score[i]
}
if ok && ans < t {
ans = t
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Backtracking | Time Complexity: O(2^n). |
| Approach 2: Dynamic Programming | Time Complexity: O(n * 2^n). |
| Binary Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(2^n * 26) | O(26 + n) | Best for interviews and small word counts where recursive subset exploration with pruning is clear and efficient. |
| Dynamic Programming with Bitmask | O(2^n * 26) | O(2^n) | Useful when modeling subsets explicitly with bitmasks or when implementing an iterative subset DP solution. |
Frequently asked questions
Is Maximum Score Words Formed by Letters easy or hard?
The problem is labeled Hard because it combines subset enumeration, scoring logic, and constraint validation. The underlying idea is manageable once you recognize that the number of words is small, making backtracking or bitmask enumeration feasible.
How to solve Maximum Score Words Formed by Letters in O(n)?
An O(n) solution is not possible because the problem requires evaluating combinations of words. The optimal solutions examine subsets of the word list, leading to O(2^n) complexity. Efficient implementations reduce constant factors using frequency arrays and pruning invalid branches early.
What is the best approach for Maximum Score Words Formed by Letters?
Backtracking is the most practical approach. The algorithm recursively decides whether to include or skip each word while tracking remaining letter frequencies. Since the number of words is small (up to 14), exploring all subsets with pruning works efficiently with time complexity O(2^n * 26).
What data structure is used in Maximum Score Words Formed by Letters?
The core data structures are frequency arrays for tracking character counts and recursion stacks for exploring subsets. Some implementations also use bitmasks to represent subsets of words efficiently in dynamic programming solutions.
What is the time complexity of Maximum Score Words Formed by Letters?
Both common solutions run in O(2^n * 26) time, where n is the number of words. Each subset of words is evaluated, and character frequency checks take up to 26 operations. Space complexity is O(26 + n) for backtracking and O(2^n) for the bitmask DP approach.
Maximum Score Words Formed by Letters Python or Java solution approach?
Python and Java implementations typically use recursive backtracking with an integer array of size 26 to store letter counts. Each recursive step attempts to include the current word, updates the counts, computes the score, and backtracks after exploring the branch.
Is Maximum Score Words Formed by Letters asked at Google, Amazon, or Meta?
Subset search and backtracking problems similar to this one appear in interviews at companies like Google, Amazon, and Meta. The question tests recursive exploration, pruning invalid states, and efficient use of frequency arrays for constraint checking.