# Maximum Score Words Formed by Letters
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-score-words-formed-by-letters)
Canonical: https://scaleengineer.com/dsa/problems/maximum-score-words-formed-by-letters
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array, String
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## 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 <= 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
## Brute Force by Generating All Subsets
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.
**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).
**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.
### Explanation
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`):
1. We start with a fresh copy of the available letter counts.
2. We iterate through all the words. If a word is part of the current subset, we check if we have enough letters for it.
3. 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.
4. If we don't have enough letters, the subset is invalid, and we discard it and move to the next one.
5. 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:
```java
class Solution {
    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        int[] letterCounts = new int[26];
        for (char c : letters) {
            letterCounts[c - 'a']++;
        }

        int n = words.length;
        int maxScore = 0;

        // Iterate through all 2^n subsets of words using a bitmask
        for (int i = 0; i < (1 << n); i++) {
            int currentScore = 0;
            int[] tempLetterCounts = letterCounts.clone();
            boolean isValidSubset = true;

            // Check each word in the current subset
            for (int j = 0; j < n; j++) {
                // If j-th word is in the subset (j-th bit is set)
                if ((i & (1 << j)) != 0) {
                    String word = words[j];
                    int wordScore = 0;
                    int[] wordCounts = new int[26];
                    
                    // Calculate word's letter requirements and score
                    for (char c : word.toCharArray()) {
                        wordCounts[c - 'a']++;
                        wordScore += score[c - 'a'];
                    }

                    // Check if we have enough letters for this word
                    boolean canFormWord = true;
                    for (int k = 0; k < 26; k++) {
                        if (wordCounts[k] > tempLetterCounts[k]) {
                            canFormWord = false;
                            break;
                        }
                    }

                    if (canFormWord) {
                        // If yes, update score and letter counts for this subset
                        for (int k = 0; k < 26; k++) {
                            tempLetterCounts[k] -= wordCounts[k];
                        }
                        currentScore += wordScore;
                    } else {
                        // If any word in the subset cannot be formed, the whole subset is invalid
                        isValidSubset = false;
                        break;
                    }
                }
            }

            if (isValidSubset) {
                maxScore = Math.max(maxScore, currentScore);
            }
        }
        return maxScore;
    }
}
```
### 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`.

## Backtracking (Depth-First Search)
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.
**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).
**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.
### Explanation
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:
```java
class Solution {
    private int maxScore = 0;

    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        int[] letterCounts = new int[26];
        for (char c : letters) {
            letterCounts[c - 'a']++;
        }
        backtrack(0, 0, words, letterCounts, score);
        return maxScore;
    }

    private void backtrack(int index, int currentScore, String[] words, int[] letterCounts, int[] score) {
        if (index == words.length) {
            maxScore = Math.max(maxScore, currentScore);
            return;
        }

        // Decision 1: Exclude words[index]
        backtrack(index + 1, currentScore, words, letterCounts, score);

        // Decision 2: Try to include words[index]
        String word = words[index];
        int wordScore = 0;
        int[] wordCount = new int[26];
        for (char c : word.toCharArray()) {
            wordCount[c - 'a']++;
            wordScore += score[c - 'a'];
        }

        boolean possible = true;
        for (int i = 0; i < 26; i++) {
            if (wordCount[i] > letterCounts[i]) {
                possible = false;
                break;
            }
        }

        if (possible) {
            // Modify state
            for (int i = 0; i < 26; i++) {
                letterCounts[i] -= wordCount[i];
            }
            
            // Recurse
            backtrack(index + 1, currentScore + wordScore, words, letterCounts, score);
            
            // Backtrack state
            for (int i = 0; i < 26; i++) {
                letterCounts[i] += wordCount[i];
            }
        }
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int maxScoreWords(String[] words, char[] letters, int[] score) {
    int[] cnt = new int[26];
    for (int i = 0; i < letters.length; ++i) {
      cnt[letters[i] - 'a']++;
    }
    int n = words.length;
    int ans = 0;
    for (int i = 0; i < 1 << n; ++i) {
      int[] cur = new int[26];
      for (int j = 0; j < n; ++j) {
        if (((i >> j) & 1) == 1) {
          for (int k = 0; k < words[j].length(); ++k) {
            cur[words[j].charAt(k) - 'a']++;
          }
        }
      }
      boolean ok = true;
      int t = 0;
      for (int j = 0; j < 26; ++j) {
        if (cur[j] > cnt[j]) {
          ok = false;
          break;
        }
        t += cur[j] * score[j];
      }
      if (ok && ans < t) {
        ans = t;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxScoreWords(vector<string> &words, vector<char> &letters,
                    vector<int> &score) {
    int cnt[26]{};
    for (char &c : letters) {
      cnt[c - 'a']++;
    }
    int n = words.size();
    int ans = 0;
    for (int i = 0; i < 1 << n; ++i) {
      int cur[26]{};
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {
          for (char &c : words[j]) {
            cur[c - 'a']++;
          }
        }
      }
      bool ok = true;
      int t = 0;
      for (int j = 0; j < 26; ++j) {
        if (cur[j] > cnt[j]) {
          ok = false;
          break;
        }
        t += cur[j] * score[j];
      }
      if (ok && ans < t) {
        ans = t;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```