Scale Engineer

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 ProgrammingBacktrackingBit ManipulationBitmask
Data structures
ArrayString
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):

  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:

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;    }}

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.

Solutions

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;  }}

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 →

Next problem