How to Solve Maximum Score Words Formed by Letters

Use backtracking combined with state transition dynamic programming to evaluate every valid subset of words efficiently. Precompute letter frequencies to quickly check feasibility of forming each word, and recursively accumulate scores while avoiding repeated use of letters. This approach ensures all combinations are considered, leveraging the small input size to explore every subset without exceeding time constraints.

Problem Statement

You are given an array of strings representing words, an array of characters representing available letters (letters may appear multiple times), and an array of integers representing the score for each letter 'a' to 'z'. Your task is to select a subset of words such that each word can be formed using the available letters, with each letter used at most once, and maximize the total score.

Return the highest total score possible by forming valid words from the letters. Each word can only be used once, it is not necessary to use all letters, and the score of a word is the sum of its letters' assigned scores.

Examples

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

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

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

Letter "e" can only be used once.

Constraints

• 1 <= words.length <= 14
• 1 <= words[i].length <= 15
• 1 <= letters.length <= 100
• letters[i].length == 1
• score.length == 26
• 0 <= score[i] <= 10
• words[i], letters[i] contains only lower case English letters.

Solution Approach

Precompute Letter Counts and Word Scores

Count the frequency of each letter in the available letters array and compute the score of each word based on individual letter scores. This allows constant-time checking of whether a word can be formed and quick calculation of incremental scores during recursion.

Backtracking with Subset Enumeration

Iterate over all subsets of words using recursion or bitmasking. For each subset, verify that all words can be formed with the remaining letters. If feasible, sum the scores and update the maximum score. This leverages the small input size (words.length <= 14) to explore 2^N combinations efficiently.

State Transition Dynamic Programming Optimization

Use a DP cache keyed by current letter availability or subset bitmask to avoid recalculating scores for previously encountered states. This ensures repeated states in the recursive exploration are skipped, significantly reducing unnecessary computations.

Complexity Analysis

Time complexity is O(2^W * (L + A)) where W is the number of words, L is the maximum word length, and A is the alphabet size (26). Space complexity is O(A + W) to store letter counts and DP cache for state transitions.

What Interviewers Usually Probe

• Look for state transition DP usage over naive backtracking.
• Check how efficiently the candidate handles word feasibility checks using letter counts.
• Observe if the candidate considers pruning invalid subsets to avoid redundant recursion.

Common Pitfalls or Variants

Common pitfalls

• Attempting to generate all permutations of letters instead of word subsets, causing exponential blowup.
• Failing to handle repeated letters correctly, leading to invalid word formation.
• Not caching intermediate results, which results in unnecessary recomputation of subset scores.

Follow-up variants

• Max score with repeated words allowed, adjusting DP accordingly.
• Words have additional constraints like mandatory inclusion of specific letters.
• Score function changes to include multipliers or penalties for certain letters.

How GhostInterview Helps

• GhostInterview provides detailed step-by-step guidance on subset enumeration for this problem.
• It highlights letter count precomputation and DP caching specific to Maximum Score Words Formed by Letters.
• Offers insights on avoiding common recursion and pruning errors when forming words from letters.

Topic Pages

• Array
• String
• Dynamic Programming
• Backtracking
• Bit Manipulation
• Bitmask

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main strategy for Maximum Score Words Formed by Letters?

Use backtracking with state transition dynamic programming to explore all valid word subsets efficiently.

Why is bitmasking useful in this problem?

Bitmasking allows representing subsets of words efficiently and is essential for DP caching of states during recursion.

How do I handle repeated letters in the letters array?

Precompute letter frequencies and decrement counts when a word uses letters; only proceed if all required letters are available.

What makes this problem suitable for state transition dynamic programming?

The small words.length lets you enumerate all subsets, and caching based on letter availability avoids recomputation, a classic DP state transition pattern.

Can all letters be used to maximize score?

Not necessarily; some letters may not contribute to high-scoring words. The goal is to maximize total score, not use all letters.