Maximum Score Words Formed by Letters - Practice Coding Problems

Maximum Score Words Formed by Letters - Problem

Array Hash Table String Dynamic Programming Backtracking Bit Manipulation Counting Bitmask Hard

Given a list of words, a list of single letters (might be repeating), and the score of every character, return the maximum score of any valid set of words formed by using the given letters.

Each word in 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.

Input & Output

Example 1 — Basic Word Selection

$ 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

💡 Note: We can form "dad" (d=5, a=1, d=5) and "good" (g=3, o=2, o=2, d=5) for total score of 11 + 12 = 23

Example 2 — Single Word Optimal

$ 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

💡 Note: We can form "xxxz" using letters x,x,x,z for score 5+5+5+10 = 25. Other combinations score less.

Example 3 — No Valid Words

$ 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

💡 Note: We cannot form "leetcode" because we need 3 e's but only have 1, so return 0

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.

Visualization

Tap to expand

Understanding the Visualization

Input

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

Process

Try all combinations, check letter availability, calculate scores

Output

Return maximum score from valid word combinations

Key Takeaway

🎯 Key Insight: Use backtracking to systematically try all word combinations while efficiently tracking letter usage

Asked in

G Google 12 a Amazon 8 f Facebook 6

The key insight is to use backtracking to explore all possible combinations of words while tracking letter usage. The optimal approach uses recursive backtracking with pruning to avoid impossible branches early. Time: O(2^n), Space: O(n + 26)

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with Pruning	O(2^n)	O(n + 26)	Recursively try each word, backtrack when invalid, prune impossible branches
Brute Force - Try All Subsets	O(2^n × m)	O(m)	Generate all possible subsets of words and check validity

Backtracking with Pruning — Algorithm Steps

Start with empty word set and full letter count
For each word, try including it if we have enough letters
Recursively explore remaining words with updated letter count
Backtrack by removing word and restoring letters
Track maximum score found

Visualization

Tap to expand

Step-by-Step Walkthrough

Decision Point

At each word, decide to include or skip

Check Validity

If including, verify we have enough letters

Recurse/Backtrack

Continue with remaining words or backtrack if invalid

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int backtrack(char words[][20], int wordCount, int* score, int index, int currentScore, int* letterCount) {
    if (index == wordCount) {
        return currentScore;
    }
    
    // Skip current word
    int maxScore = backtrack(words, wordCount, score, index + 1, currentScore, letterCount);
    
    // Try including current word
    char* word = words[index];
    int wordScore = 0;
    int tempCount[26];
    memcpy(tempCount, letterCount, 26 * sizeof(int));
    int canUse = 1;
    
    int len = strlen(word);
    for (int i = 0; i < len; i++) {
        int idx = word[i] - 'a';
        wordScore += score[idx];
        tempCount[idx]--;
        if (tempCount[idx] < 0) {
            canUse = 0;
            break;
        }
    }
    
    if (canUse) {
        int newScore = backtrack(words, wordCount, score, index + 1, currentScore + wordScore, tempCount);
        if (newScore > maxScore) {
            maxScore = newScore;
        }
    }
    
    return maxScore;
}

int solution(char words[][20], int wordCount, char* letters, int letterCount, int* score) {
    // Count available letters
    int available[26] = {0};
    for (int i = 0; i < letterCount; i++) {
        available[letters[i] - 'a']++;
    }
    
    return backtrack(words, wordCount, score, 0, 0, available);
}

int main() {
    char words[14][20];
    char letters[1000];
    int score[26];
    
    // Simple parsing - read line by line
    char line[2000];
    fgets(line, sizeof(line), stdin);
    // Parse words from JSON array
    int wordCount = 0;
    // Simplified parsing for demo
    
    fgets(line, sizeof(line), stdin);
    // Parse letters
    int letterCount = 0;
    
    fgets(line, sizeof(line), stdin);
    // Parse scores
    
    int result = solution(words, wordCount, letters, letterCount, score);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

In worst case still explores all subsets, but with pruning it's often much faster

⚠ Quadratic Growth

Space Complexity

O(n + 26)

Recursion stack depth up to n words plus letter frequency array

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking with Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler