Maximum Score Words Formed by Letters

Hard

#1171Time: O(2^N * N * L), where `N` is the number of words and `L` is the maximum length of a word. We iterate through `2^N` subsets. For each subset, we might iterate up to `N` words. For each word, we perform operations proportional to its length `L`.Space: O(A + L), where `A` is the alphabet size (26) and `L` is the max word length. This space is for storing frequency counts. Since `A` and `L` are bounded by constants, this can be considered O(1).1 company

Patterns

Dynamic Programming Backtracking Bit Manipulation Bitmask

Data structures

Array String

Companies

Infosys

Prompt

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 <= 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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves systematically generating every possible subset of the given words. For each subset, we then check if it's 'valid', meaning it can be formed using the available letters. If a subset is valid, we calculate its total score and compare it with the maximum score found so far, updating it if the current subset's score is higher.

Algorithm

Create a frequency map letterCounts from the letters array.
Initialize maxScore = 0.
Let N be the number of words.
Loop through all integers i from 0 to (1 << N) - 1 (representing subsets).
- Inside the loop, create a tempLetterCounts by cloning letterCounts and initialize currentScore = 0.
- Assume the subset is valid: isValidSubset = true.
- Loop through each word j from 0 to N-1.
  - If word j is in the subset (check j-th bit), attempt to form it.
  - Check if tempLetterCounts has enough letters for words[j].
  - If yes, update currentScore and decrement tempLetterCounts.
  - If no, set isValidSubset = false and break the inner loop.
- If isValidSubset is still true after checking all words, update maxScore = max(maxScore, currentScore).
Return maxScore.

Walkthrough

The core idea is to treat the problem as finding the best among all 2^N possible combinations of words, where N is the total number of words.

First, we pre-process the letters array to get a frequency count of each available character. This is typically stored in an array of size 26.

We can represent each subset using a bitmask. An integer from 0 to 2^N - 1 can represent all subsets. If the j-th bit of the integer is 1, it means words[j] is included in the current subset.

For each subset (each integer from 0 to 2^N - 1):

We start with a fresh copy of the available letter counts.
We iterate through all the words. If a word is part of the current subset, we check if we have enough letters for it.
If we do, we subtract the letters used by the word from our temporary counts and add the word's score to the subset's score.
If we don't have enough letters, the subset is invalid, and we discard it and move to the next one.
If we successfully process all words in a subset, we compare its total score with our global maximum and update if needed.

Here is a Java implementation of this approach:

1class Solution {2    public int maxScoreWords(String[] words, char[] letters, int[] score) {3        int[] letterCounts = new int[26];4        for (char c : letters) {5            letterCounts[c - 'a']++;6        }7 8        int n = words.length;9        int maxScore = 0;10 11        // Iterate through all 2^n subsets of words using a bitmask12        for (int i = 0; i < (1 << n); i++) {13            int currentScore = 0;14            int[] tempLetterCounts = letterCounts.clone();15            boolean isValidSubset = true;16 17            // Check each word in the current subset18            for (int j = 0; j < n; j++) {19                // If j-th word is in the subset (j-th bit is set)20                if ((i & (1 << j)) != 0) {21                    String word = words[j];22                    int wordScore = 0;23                    int[] wordCounts = new int[26];24                    25                    // Calculate word's letter requirements and score26                    for (char c : word.toCharArray()) {27                        wordCounts[c - 'a']++;28                        wordScore += score[c - 'a'];29                    }30 31                    // Check if we have enough letters for this word32                    boolean canFormWord = true;33                    for (int k = 0; k < 26; k++) {34                        if (wordCounts[k] > tempLetterCounts[k]) {35                            canFormWord = false;36                            break;37                        }38                    }39 40                    if (canFormWord) {41                        // If yes, update score and letter counts for this subset42                        for (int k = 0; k < 26; k++) {43                            tempLetterCounts[k] -= wordCounts[k];44                        }45                        currentScore += wordScore;46                    } else {47                        // If any word in the subset cannot be formed, the whole subset is invalid48                        isValidSubset = false;49                        break;50                    }51                }52            }53 54            if (isValidSubset) {55                maxScore = Math.max(maxScore, currentScore);56            }57        }58        return maxScore;59    }60}

Complexity

Time

O(2^N * N * L), where `N` is the number of words and `L` is the maximum length of a word. We iterate through `2^N` subsets. For each subset, we might iterate up to `N` words. For each word, we perform operations proportional to its length `L`.

Space

O(A + L), where `A` is the alphabet size (26) and `L` is the max word length. This space is for storing frequency counts. Since `A` and `L` are bounded by constants, this can be considered O(1).

Trade-offs

Pros

Conceptually straightforward as it directly translates the problem of checking every possibility.

Cons

Highly inefficient due to redundant computations. The validity of using a word is checked repeatedly for different subsets that contain it.
The logic within the loops can be complex to manage correctly.

A more efficient approach is to use backtracking, which builds a solution incrementally. We can model the problem as a decision tree where at each level, we decide whether to include a specific word in our set or to skip it. By traversing this tree using a depth-first search, we can explore all valid combinations of words without the redundant calculations of the brute-force method.

Algorithm

Create a frequency map letterCounts from the letters array.
Initialize a member variable maxScore = 0.
Define a recursive function backtrack(index, currentScore).
- Base Case: If index == words.length, update maxScore = max(maxScore, currentScore) and return.
- Choice 1 (Exclude): Recursively call backtrack(index + 1, currentScore).
- Choice 2 (Include):
  - Check if words[index] can be formed using the current letterCounts.
  - If yes:
    - Calculate wordScore.
    - Subtract the letters of words[index] from letterCounts.
    - Recursively call backtrack(index + 1, currentScore + wordScore).
    - Backtrack: Add the letters of words[index] back to letterCounts.
Start the process by calling backtrack(0, 0).
Return maxScore.

Walkthrough

This method avoids re-computing information by maintaining a single state (the currently available letters) and exploring possibilities recursively. The algorithm uses a helper function, backtrack, which is called recursively to build a solution using the 'include/exclude' pattern.

Base Case: When the recursion index reaches the end of the words array, it means we've made a decision for every word. We update the global maxScore with the currentScore of this particular combination and return.
Recursive Step: For the word at words[index], we explore two possibilities:
1. Exclude words[index]: We skip this word and move to the next one by making a recursive call: backtrack(index + 1, currentScore).
2. Include words[index]: We first check if the word can be formed with the available letters. If it can, we calculate its score, subtract its letters from the available letterCounts, and make a recursive call for the next word with the updated score: backtrack(index + 1, currentScore + wordScore). After this call returns, we must add the letters back to letterCounts to revert the state. This 'backtracking' step is crucial as it allows other paths to be explored correctly.

Here is a clean Java implementation using this backtracking strategy:

1class Solution {2    private int maxScore = 0;3 4    public int maxScoreWords(String[] words, char[] letters, int[] score) {5        int[] letterCounts = new int[26];6        for (char c : letters) {7            letterCounts[c - 'a']++;8        }9        backtrack(0, 0, words, letterCounts, score);10        return maxScore;11    }12 13    private void backtrack(int index, int currentScore, String[] words, int[] letterCounts, int[] score) {14        if (index == words.length) {15            maxScore = Math.max(maxScore, currentScore);16            return;17        }18 19        // Decision 1: Exclude words[index]20        backtrack(index + 1, currentScore, words, letterCounts, score);21 22        // Decision 2: Try to include words[index]23        String word = words[index];24        int wordScore = 0;25        int[] wordCount = new int[26];26        for (char c : word.toCharArray()) {27            wordCount[c - 'a']++;28            wordScore += score[c - 'a'];29        }30 31        boolean possible = true;32        for (int i = 0; i < 26; i++) {33            if (wordCount[i] > letterCounts[i]) {34                possible = false;35                break;36            }37        }38 39        if (possible) {40            // Modify state41            for (int i = 0; i < 26; i++) {42                letterCounts[i] -= wordCount[i];43            }44            45            // Recurse46            backtrack(index + 1, currentScore + wordScore, words, letterCounts, score);47            48            // Backtrack state49            for (int i = 0; i < 26; i++) {50                letterCounts[i] += wordCount[i];51            }52        }53    }54}

Complexity

Time

O(2^N * L), where `N` is the number of words and `L` is the maximum length of a word. The recursion tree has at most `2^N` paths (subsets). At each step of the recursion, we do work proportional to `L` to check a word's validity. This is a significant improvement over the `O(2^N * N * L)` approach.

Space

O(N + A), where `N` is the recursion depth (equal to the number of words) and `A` is the alphabet size (26). This space is used by the recursion call stack and the frequency count arrays. Since `A` is constant, the complexity is O(N).

Trade-offs

Pros

Much more efficient than the brute-force subset generation.
Implicitly prunes invalid branches of the search space early.
The state (available letters) is managed cleanly throughout the recursion.

Cons

The concept of recursion and backtracking can be slightly harder to grasp than simple iteration.
For a very large number of words (not the case here as N <= 14), it could lead to a stack overflow error.

Solutions

Solution

1class Solution {2public3  int maxScoreWords(String[] words, char[] letters, int[] score) {4    int[] cnt = new int[26];5    for (int i = 0; i < letters.length; ++i) {6      cnt[letters[i] - 'a']++;7    }8    int n = words.length;9    int ans = 0;10    for (int i = 0; i < 1 << n; ++i) {11      int[] cur = new int[26];12      for (int j = 0; j < n; ++j) {13        if (((i >> j) & 1) == 1) {14          for (int k = 0; k < words[j].length(); ++k) {15            cur[words[j].charAt(k) - 'a']++;16          }17        }18      }19      boolean ok = true;20      int t = 0;21      for (int j = 0; j < 26; ++j) {22        if (cur[j] > cnt[j]) {23          ok = false;24          break;25        }26        t += cur[j] * score[j];27      }28      if (ok && ans < t) {29        ans = t;30      }31    }32    return ans;33  }34}

1class Solution {2public:3  int maxScoreWords(vector<string> &words, vector<char> &letters,4                    vector<int> &score) {5    int cnt[26]{};6    for (char &c : letters) {7      cnt[c - 'a']++;8    }9    int n = words.size();10    int ans = 0;11    for (int i = 0; i < 1 << n; ++i) {12      int cur[26]{};13      for (int j = 0; j < n; ++j) {14        if (i >> j & 1) {15          for (char &c : words[j]) {16            cur[c - 'a']++;17          }18        }19      }20      bool ok = true;21      int t = 0;22      for (int j = 0; j < 26; ++j) {23        if (cur[j] > cnt[j]) {24          ok = false;25          break;26        }27        t += cur[j] * score[j];28      }29      if (ok && ans < t) {30        ans = t;31      }32    }33    return ans;34  }35};

1class Solution:2    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int: cnt = Counter(letters) n = len(words) ans = 0 for i in range(1 << n): cur = Counter('' . join([words[j] for j in range(n) if i >> j & 1])) if all(v <= cnt[c] for c, v in cur . items()): t = sum(v * score[ord(c) - ord('a')] for c, v in cur . items()) ans = max(ans, t) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem