LeetCode 1255 - Maximum Score Words Formed by Letters

This problem asks us to select a subset of words that can be constructed using a limited supply of letters, such that th

leetcodehardarrayhash-tablestringdynamic-programmingbacktrackingbit-manipulationcountingbitmask

LeetCode Problem 1255

Difficulty: 🔴 Hard
Topics: Array, Hash Table, String, Dynamic Programming, Backtracking, Bit Manipulation, Counting, Bitmask

Solution

Problem Understanding

This problem asks us to select a subset of words that can be constructed using a limited supply of letters, such that the total score of all chosen words is maximized.

We are given three inputs:

  • words, an array of strings
  • letters, a multiset of available characters
  • score, an array of 26 integers where score[i] represents the value of the character 'a' + i

Each word may either be selected once or not selected at all. A word can only be used if every character it requires is available in the remaining letter supply. Every letter in letters may only be used once across all chosen words.

The goal is to compute the maximum total score achievable by choosing any valid subset of words.

The important observation is that this is fundamentally a subset selection problem. For every word, we have two choices:

  • Include the word
  • Skip the word

Since words.length <= 14, the total number of subsets is at most:

$$2^{14} = 16384$$

This is small enough for exhaustive exploration with pruning or backtracking.

The constraints also tell us several useful things:

  • The number of words is very small, which strongly suggests subset enumeration or backtracking.
  • Word lengths are small enough that counting character frequencies is inexpensive.
  • The total number of letters can be larger, but only 26 lowercase letters exist, so frequency arrays are efficient.

Several edge cases are important:

  • Some words may be impossible to form even individually.
  • The optimal solution may skip high scoring words if they consume letters needed by better combinations.
  • The answer can be 0 if no valid word can be formed.
  • Multiple words may compete for the same limited letters.
  • Letter scores can be zero, meaning some letters contribute nothing.

A naive greedy strategy fails because local decisions do not guarantee a globally optimal subset.

Approaches

Brute Force Approach

The most direct solution is to generate every possible subset of words.

For each subset:

  1. Count the total frequency of letters needed.
  2. Compare those frequencies against the available letters.
  3. If valid, compute the total score.
  4. Track the maximum score.

This works because every possible combination is evaluated, guaranteeing that the optimal subset is considered.

However, this approach repeatedly recomputes frequencies and scores from scratch for each subset. While the total number of subsets is manageable, redundant computation makes the implementation less efficient.

Optimal Approach, Backtracking with Incremental State

The better solution uses backtracking.

Instead of rebuilding counts for every subset independently, we process words one at a time and maintain the current letter usage incrementally.

At each index:

  • Skip the current word
  • Try including the current word if enough letters remain

This creates a decision tree with at most $2^n$ states.

The key insight is that:

  • The number of words is very small
  • The alphabet size is fixed at 26
  • We can efficiently maintain letter frequencies during recursion

By updating counts incrementally, we avoid repeated recomputation and achieve an efficient exhaustive search.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n × n × 26) O(26) Recomputes frequencies for every subset
Optimal O(2^n × 26) O(26 + n) Backtracking with incremental frequency tracking

Here, n is the number of words.

Algorithm Walkthrough

Step 1: Count Available Letters

Create a frequency array of size 26 representing how many times each letter is available.

For example:

letters = ["a","a","c","d","d","d","g","o","o"]

becomes:

a -> 2
c -> 1
d -> 3
g -> 1
o -> 2

Using a fixed-size array is faster and simpler than a hash map because only lowercase English letters exist.

Step 2: Precompute Word Information

For every word:

  • Compute its letter frequency array
  • Compute its total score

This avoids recalculating them during recursion.

For "dad":

d -> 2
a -> 1
score = 5 + 1 + 5 = 11

Step 3: Define the Recursive Decision Function

We recursively process words by index.

At each position, we have two choices:

  1. Skip the word
  2. Include the word if enough letters remain

The recursive function returns the maximum score achievable from the current index onward.

Step 4: Try Skipping the Current Word

We first compute the result without using the current word:

best = dfs(index + 1)

This explores all subsets that exclude the current word.

Step 5: Check Whether the Word Can Be Used

Compare the word's letter requirements against the remaining available letters.

If any required count exceeds availability, the word cannot be included.

Step 6: Include the Word

If the word is valid:

  1. Subtract its letters from the available counts
  2. Add its score
  3. Recurse to the next index
  4. Restore the counts afterward

This restoration step is essential because backtracking reuses the same frequency array for different branches.

Step 7: Return the Best Result

Return the maximum score between:

  • Skipping the word
  • Including the word

Why it works

The algorithm explores every valid subset of words through recursive inclusion and exclusion decisions. Because every subset corresponds to exactly one path in the recursion tree, the optimal subset is guaranteed to be examined.

The frequency array always correctly represents the remaining available letters because every recursive inclusion subtracts counts and every backtrack restores them. This invariant guarantees that validity checks are always accurate.

Python Solution

from typing import List

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

        word_counts = []
        word_scores = []

        for word in words:
            counts = [0] * 26
            total_score = 0

            for ch in word:
                idx = ord(ch) - ord('a')
                counts[idx] += 1
                total_score += score[idx]

            word_counts.append(counts)
            word_scores.append(total_score)

        n = len(words)

        def dfs(index: int) -> int:
            if index == n:
                return 0

            best = dfs(index + 1)

            can_use = True
            counts = word_counts[index]

            for i in range(26):
                if counts[i] > available[i]:
                    can_use = False
                    break

            if can_use:
                for i in range(26):
                    available[i] -= counts[i]

                best = max(
                    best,
                    word_scores[index] + dfs(index + 1)
                )

                for i in range(26):
                    available[i] += counts[i]

            return best

        return dfs(0)

The implementation begins by building the available frequency array from the input letters. This allows constant-time access to remaining letter counts.

Next, the solution preprocesses every word. Two arrays are created:

  • word_counts, storing the frequency array for each word
  • word_scores, storing the total score for each word

This preprocessing prevents repeated work during recursion.

The recursive dfs function explores all subset choices. The base case occurs when all words have been processed.

For each word, the function first computes the result obtained by skipping it. Then it checks whether the word can be formed using the currently available letters.

If the word is valid, its letters are temporarily removed from the frequency array, recursion continues, and afterward the letters are restored. This restoration is the core backtracking mechanism.

Finally, the function returns the larger score between the include and exclude choices.

Go Solution

func maxScoreWords(words []string, letters []byte, score []int) int {
	available := make([]int, 26)

	for _, ch := range letters {
		available[ch-'a']++
	}

	n := len(words)

	wordCounts := make([][]int, n)
	wordScores := make([]int, n)

	for i, word := range words {
		counts := make([]int, 26)
		totalScore := 0

		for _, ch := range word {
			idx := ch - 'a'
			counts[idx]++
			totalScore += score[idx]
		}

		wordCounts[i] = counts
		wordScores[i] = totalScore
	}

	var dfs func(int) int

	dfs = func(index int) int {
		if index == n {
			return 0
		}

		best := dfs(index + 1)

		counts := wordCounts[index]
		canUse := true

		for i := 0; i < 26; i++ {
			if counts[i] > available[i] {
				canUse = false
				break
			}
		}

		if canUse {
			for i := 0; i < 26; i++ {
				available[i] -= counts[i]
			}

			withCurrent := wordScores[index] + dfs(index+1)

			if withCurrent > best {
				best = withCurrent
			}

			for i := 0; i < 26; i++ {
				available[i] += counts[i]
			}
		}

		return best
	}

	return dfs(0)
}

The Go implementation follows the same logic as the Python version but uses slices instead of Python lists.

One notable difference is that Go uses explicit integer comparisons instead of Python's built-in max() function.

The frequency arrays are represented as []int slices of length 26. Because slices are mutable references, the backtracking restoration step is especially important to avoid corrupting shared state across recursive branches.

Go integers are fully sufficient for this problem because the maximum possible score is small relative to integer limits.

Worked Examples

Example 1

words = ["dog","cat","dad","good"]
letters = ["a","a","c","d","d","d","g","o","o"]

Available counts:

Letter Count
a 2
c 1
d 3
g 1
o 2

Word scores:

Word Score
dog 10
cat 10
dad 11
good 12

The recursion explores all subsets.

Consider the optimal branch:

Step Action Remaining Letters Total Score
1 Take "dad" a=1,d=1,g=1,o=2,c=1 11
2 Take "good" a=1,d=0,g=0,o=0,c=1 23

No better valid subset exists.

Final answer:

23

Example 2

words = ["xxxz","ax","bx","cx"]

Scores:

Letter Score
a 4
b 4
c 4
x 5
z 10

Possible choices:

Subset Score
xxxz 25
ax + bx + cx 27

The recursive search discovers that using three separate words produces a larger total score.

Final answer:

27

Example 3

words = ["leetcode"]
letters = ["l","e","t","c","o","d"]

The word requires:

e -> 3

but only one 'e' exists.

The validity check fails, so the word cannot be included.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(2^n × 26) Each recursive state checks at most 26 letters
Space O(26 + n) Frequency arrays plus recursion stack

The recursion generates at most $2^n$ states because each word has two choices, include or exclude.

At every state, the algorithm performs at most 26 operations for frequency checking and updates, since only lowercase English letters exist.

The space complexity consists of:

  • The frequency arrays of size 26
  • The recursion stack of depth n

Since n <= 14, the recursion depth remains very small.

Test Cases

from typing import List

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

        word_counts = []
        word_scores = []

        for word in words:
            counts = [0] * 26
            total_score = 0

            for ch in word:
                idx = ord(ch) - ord('a')
                counts[idx] += 1
                total_score += score[idx]

            word_counts.append(counts)
            word_scores.append(total_score)

        n = len(words)

        def dfs(index: int) -> int:
            if index == n:
                return 0

            best = dfs(index + 1)

            counts = word_counts[index]
            can_use = True

            for i in range(26):
                if counts[i] > available[i]:
                    can_use = False
                    break

            if can_use:
                for i in range(26):
                    available[i] -= counts[i]

                best = max(
                    best,
                    word_scores[index] + dfs(index + 1)
                )

                for i in range(26):
                    available[i] += counts[i]

            return best

        return dfs(0)

sol = Solution()

# Example 1
assert sol.maxScoreWords(
    ["dog","cat","dad","good"],
    ["a","a","c","d","d","d","g","o","o"],
    [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]
) == 23  # standard example

# Example 2
assert sol.maxScoreWords(
    ["xxxz","ax","bx","cx"],
    ["z","a","b","c","x","x","x"],
    [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]
) == 27  # combination beats single high-value word

# Example 3
assert sol.maxScoreWords(
    ["leetcode"],
    ["l","e","t","c","o","d"],
    [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]
) == 0  # impossible word

# Single valid word
assert sol.maxScoreWords(
    ["abc"],
    ["a","b","c"],
    [1] * 26
) == 3  # exact letter match

# Single invalid word
assert sol.maxScoreWords(
    ["abc"],
    ["a","b"],
    [1] * 26
) == 0  # missing character

# Choose best subset instead of all words
assert sol.maxScoreWords(
    ["a","aa","aaa"],
    ["a","a","a"],
    [1] * 26
) == 3  # best is "aaa"

# Zero score letters
assert sol.maxScoreWords(
    ["abc"],
    ["a","b","c"],
    [0] * 26
) == 0  # all letters worth zero

# Multiple competing combinations
assert sol.maxScoreWords(
    ["ab","bc","abc"],
    ["a","b","c"],
    [1] * 26
) == 3  # choose "abc"

# Repeated letters across words
assert sol.maxScoreWords(
    ["aa","bb","ab"],
    ["a","a","b","b"],
    [1] * 26
) == 4  # choose "aa" + "bb"

# Empty effective solution
assert sol.maxScoreWords(
    ["zzz"],
    ["a","b","c"],
    [1] * 26
) == 0  # no valid words
Test Why
Example 1 Validates standard mixed subset selection
Example 2 Confirms combination can beat highest scoring single word
Example 3 Validates impossible word handling
Single valid word Tests exact frequency matching
Single invalid word Tests missing character handling
Choose best subset Ensures algorithm explores all combinations
Zero score letters Confirms scoring logic works correctly
Multiple competing combinations Validates optimal subset selection
Repeated letters across words Tests shared resource constraints
Empty effective solution Ensures answer can be zero

Edge Cases

Words That Cannot Be Formed Individually

A word may require letters that do not exist in the available pool. For example:

words = ["zzz"]
letters = ["a","b","c"]

A buggy implementation might still attempt to include the word or produce a negative frequency count. This solution prevents that by validating every required letter count before inclusion.

Optimal Solution Does Not Use All Words

It may be tempting to greedily include every valid word, but this can produce suboptimal results because words compete for limited letters.

For example:

words = ["aaa", "aa", "a"]
letters = ["a","a","a"]

The best answer is "aaa" with score 3, not "aa" + "a" by coincidence of equal score, and in other scoring setups the greedy choice could fail entirely.

The recursive search guarantees every subset is evaluated.

Letters With Zero Score

Some letters may contribute nothing to the total score. A careless implementation might incorrectly prioritize longer words even if their extra letters have zero value.

For example:

score = [0] * 26

Every valid subset should return score 0.

This implementation computes exact letter-based totals and therefore handles zero-value letters naturally and correctly.