1255. Maximum Score Words Formed by Letters
Problem Description
The given problem is an optimization challenge where we have to find the maximum score achievable by forming valid sets of words from a given list. Each word has an associated score based on the characters it contains and a score table provided for the alphabet. The words come from a list called words
, and we are given a list of available single letters
which may contain duplicates. Each letter in letters
can be used only once. The score for each letter is given by an array score
, where score[0]
corresponds to the score of 'a', score[1]
to the score of 'b', and so on unto score[25]
, which corresponds to the score of 'z'.
The goal is to select words from the words
list in such a way that we can form them from the letters in the letters
list without reusing any single letter more than its available count. We cannot use any word more than once. We should return the highest possible score that can be obtained from any combination of the words formed.
Flowchart Walkthrough
Let's analyze the problem specified, LeetCode 1255. Maximum Score Words Formed by Letters, using the algorithm flowchart. Here's a detailed step-by-step process leading to the adoption of a particular algorithm pattern:
-
Is it a graph?
- Answer: No, the problem involves forming words from given characters, which does not revolve around the graph concept of nodes and links.
-
Need to solve for kth smallest/largest?
- Answer: No, the objective is to maximize score by forming words, not about finding the kth smallest or largest element.
-
Involves Linked Lists?
- Answer: No, this problem does not entail data manipulation or traversal typical of linked list operations.
-
Does the problem have small constraints?
- Answer: Yes, since the problem statement limits the number of words and letters are manageable, suggesting that exploring all combinations could be feasible.
-
Brute force / Backtracking?
- Answer: Yes, due to the small constraints and the nature of the problem where we need to explore different combinations of words that can be formed to maximize the score, a brute force approach could be viable. More precisely, backtracking is suitable for exploring all combinations of words to find the ones that gather the maximum points, considering constraints like the number of each letter available.
Conclusion: The flowchart suggests using a backtracking approach for this problem because it involves searching through combinations of words to maximize the score based on given letters and word values, under feasible constraint limits.
For a complete understanding, you can refer to the Flowchart.
Intuition
To solve the problem, we think of all possible subsets of the provided words
array. For each subset, we calculate the score of its constituent words if it's possible to create the subset with the given letters
. We only consider a subset valid if each letter required to form this subset of words is available the required number of times in the letters
list. We use bitwise operations to generate possible subsets.
Generating subsets: We use a binary representation of numbers to iterate over all possible subsets. For a list of n
words, there are 2^n
possible subsets. We can represent the subsets using a bitmask of length n
, where the j-th bit indicates whether or not to include the j-th word in the subset.
Counting letters in words: We use a data structure, Counter
, to count the occurrences of each letter in both the currently considered subset of words and the available letters.
Checking validity and score calculation: For a chosen subset, we check if it can be created with the given letters by ensuring the count of each letter in the subset does not exceed the count of available letters. If valid, we calculate the subset's score by summing the individual character scores. This is done by referring to the supplied score
array using the character's ASCII value adjusted with the ASCII value of 'a' to correctly index into the score list.
Maximizing the score: We compare each valid subset's score to the current known maximum score and update the maximum score if a higher one is found.
Optimization: Although the proposed solution methodically generates all potential subsets and assesses each one, it is not efficient for large lists of words due to its exponential time complexity. However, this brute-force approach provides a direct and complete search of the solution space, which is acceptable for smaller inputs.
Learn more about Dynamic Programming, Backtracking and Bitmask patterns.
Solution Approach
The implementation of the solution can be explained step by step as follows:
-
Initialization: A
Counter
object namedcnt
is created to store the count of each available letter in theletters
list. Next, the length of thewords
list is stored in variablen
, and a variableans
is initialized to zero to keep track of the maximum score. -
Iterating over subsets: A
for
loop is used to iterate through numbers0
to2^n - 1
representing all possible subsets wheren
is the number of words. Inside the loop, each number represents a subset where each bit in the binary representation of the number indicates the presence (1
) or absence (0
) of a word at that index in the subset. -
Building a subset: For each number
i
in the loop, we use a list comprehension to collect words corresponding to set bits in the binary representation of the number. This is done with[words[j] for j in range(n) if i >> j & 1]
. Then, aCounter
object namedcur
is created to store the count of each letter in this subset of words. -
Checking if the subset is valid: The
all
function is used to verify that for all charactersc
and their countv
in the subsetcur
, there is a sufficient number of letters incnt
(v <= cnt[c]
). This ensures that the current subset can be formed from the available letters without reusing any letter more than available. -
Calculating the score of the subset: If the subset is valid, the score is computed using the
sum
function. For each characterc
and its countv
incur
, the expressionv * score[ord(c) - ord('a')]
calculates the total score of the character in the subset by multiplying its count with its respective score inscore
. Theord
function gets the ASCII value of the character, and subtractingord('a')
gives the index of the score for that character in the score array. -
Updating the maximum score: The score of the current valid subset
t
is compared with the currentans
, and ift
is greater,ans
is updated tot
. -
Returning the result: After the loop finishes executing, the final value of
ans
is returned, which contains the maximum score obtained from any valid subset of words.
The solution uses a bitmasking technique to generate all possible subsets of words and a Counter data structure to efficiently count the occurrences of letters in both the available letters and each subset of words. The brute-force approach checks each subset for validity and calculates its score independently. Despite its simplicity, the time complexity of this solution is O(2^n * (m + k))
, where n
is the number of words, m
is the length of the longest word, and k
is the number of unique characters in letters
, which may not be performant for large datasets.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach:
Assume we have the following inputs:
words = ["dog", "cat", "dad", "good"]
letters = ["a", "a", "c", "d", "d", "g", "o", "o"]
score = [1, 0, ..., 2, ..., 0, ..., 1, ..., 0, 2] // score for "a" is 1, "c" is 2, "d" is 1, "g" is 2, "o" is 1
The score array only shows the scores for the relevant characters for brevity.
-
Initialization: We calculate the count of each letter in the
letters
list. The counter would look likecnt = {'a': 2, 'c': 1, 'd': 2, 'g': 1, 'o': 2}
. The number of wordsn = 4
, and the starting maximum scoreans = 0
. -
Iterating over subsets: We generate numbers from
0
to2^n - 1
which is from0
to15
forn = 4
. Each representation will be from0000
to1111
in binary, corresponding to taking none or all the words, respectively. -
Building a subset: When the loop is at
i = 3
(binary0011
), it indicates includingwords[0]
andwords[1]
which are "dog" and "cat". We determine the count of letters in the subset,cur = Counter("dogcat") = {'d': 1, 'o': 1, 'g': 1, 'c': 1, 'a': 1}
. -
Checking if the subset is valid: We compare
cur
againstcnt
and find that all letters incur
are less than or equal to those incnt
({'d': 1, 'o': 1, 'g': 1, 'c': 1, 'a': 1}
vs.{'a': 2, 'c': 1, 'd': 2, 'g': 1, 'o': 2}
). Therefore, the subset is valid. -
Calculating the score of the subset: The score for the subset "dogcat" is calculated as follows:
- "dog" contributes
1*score[3] + 1*score[14] + 1*score[6] = 1*1 + 1*1 + 1*2 = 4
becausescore[3]
for 'd',score[14]
for 'o', andscore[6]
for 'g'. - "cat" contributes
1*score[2] + 1*score[0] + 1*score[19] = 1*2 + 1*1 + 1*0 = 3
becausescore[2]
for 'c',score[0]
for 'a'. - Total subset score is
4 + 3 = 7
.
- "dog" contributes
-
Updating the maximum score: Since
7
is greater than0
, we updateans
to7
. -
Continuing: The loop continues, testing the validity of other subsets and updating
ans
as necessary. After testing all possible subsets, the highest score found is returned. For instance, if the algorithm later encounters the subset "good" with a higher score than7
,ans
will be updated accordingly. -
Returning the result: After completion, suppose the highest score was achieved by the subset "good" and it was
8
. Then,ans
will be8
, which is the result returned by the function.
This walkthrough exemplifies the steps and considerations of the solution approach on a smaller scale of inputs, demonstrating how the brute-force method selects and sums up word scores to find the maximum possible score given the constraints.
Solution Implementation
1from collections import Counter
2from typing import List
3
4class Solution:
5 def max_score_words(self, words: List[str], letters: List[str], score: List[int]) -> int:
6 # Count the frequency of each letter available
7 available_letter_count = Counter(letters)
8
9 # Determine the total number of words
10 number_of_words = len(words)
11
12 # Initialize the maximum score
13 maximum_score = 0
14
15 # Iterate over all combinations of words using binary representation
16 # Each bit in 'i' represents whether to include a word at that position or not
17 for i in range(1 << number_of_words):
18 # Use a Counter to track the frequency of letters in the chosen combination of words
19 current_word_count = Counter(''.join(words[j] for j in range(number_of_words) if (i >> j) & 1))
20
21 # Check if the combination of words can be built with the given letters
22 if all(current_word_count[letter] <= available_letter_count[letter] for letter in current_word_count):
23 # Calculate the score for the current combination of words
24 current_score = sum(current_word_count[letter] * score[ord(letter) - ord('a')] for letter in current_word_count)
25 # Update the maximum score if the current score is higher
26 maximum_score = max(maximum_score, current_score)
27
28 # Return the maximum score found
29 return maximum_score
30
1class Solution {
2
3 /**
4 * Calculates the maximum score achievable by forming words from the given letters.
5 *
6 * @param words An array of words to be considered for scoring.
7 * @param letters An array of letters available to form words.
8 * @param score An array representing the score for each alphabet letter.
9 * @return The maximum score achievable.
10 */
11 public int maxScoreWords(String[] words, char[] letters, int[] score) {
12 // Keep track of letter counts in the given letters array.
13 int[] letterCounts = new int[26];
14 for (char letter : letters) {
15 // Increment the count for encountered letter.
16 letterCounts[letter - 'a']++;
17 }
18
19 int wordCount = words.length;
20 int maxScore = 0; // Keep track of the maximum score.
21
22 // Loop through each combination of words possible.
23 for (int i = 0; i < (1 << wordCount); ++i) {
24 int[] currentCount = new int[26]; // To hold the count for current combination.
25 // Check each word in the current combination.
26 for (int j = 0; j < wordCount; ++j) {
27 if (((i >> j) & 1) == 1) { // Check if the j-th word is included.
28 for (char c : words[j].toCharArray()) {
29 currentCount[c - 'a']++; // Count the characters for the word.
30 }
31 }
32 }
33
34 // Verify if current combination can be made from available letters.
35 boolean isCombinationValid = true;
36 int currentScore = 0;
37 for (int j = 0; j < 26; ++j) {
38 if (currentCount[j] > letterCounts[j]) { // More letters required than available.
39 isCombinationValid = false;
40 break;
41 }
42 currentScore += currentCount[j] * score[j]; // Accumulate score for the current combination.
43 }
44
45 // Update maxScore if this combination is valid and its score is higher.
46 if (isCombinationValid && maxScore < currentScore) {
47 maxScore = currentScore;
48 }
49 }
50
51 // Return the maximum score after evaluating all combinations.
52 return maxScore;
53 }
54}
55
1class Solution {
2public:
3 // Function to calculate the maximum score of a set of words given a set of letters and their corresponding scores.
4 int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
5 int letterCounts[26] = {0}; // Array to hold counts of each letter in 'letters'
6 // Count the occurrence of each letter in 'letters'
7 for (char& letter : letters) {
8 letterCounts[letter - 'a']++; // Increment the count for the corresponding letter
9 }
10
11 int numWords = words.size(); // Total number of words
12 int maxScore = 0; // Variable to store the maximum score
13
14 // Loop through all combinations of words
15 for (int combination = 0; combination < (1 << numWords); ++combination) {
16 int wordCounts[26] = {0}; // Current letter counts for the current combination of words
17 // Build the count for the current combination
18 for (int wordIndex = 0; wordIndex < numWords; ++wordIndex) {
19 // Check if the word at wordIndex is included in the current combination
20 if (combination >> wordIndex & 1) {
21 // If so, count each letter in the word
22 for (char& letter : words[wordIndex]) {
23 wordCounts[letter - 'a']++; // Increment the count for the corresponding letter
24 }
25 }
26 }
27
28 bool isValidCombination = true; // Flag to check if the combination is valid
29 int currentScore = 0; // Score for the current combination
30 for (int letterIndex = 0; letterIndex < 26; ++letterIndex) {
31 // If any letter count exceeds what is available, the combination is invalid
32 if (wordCounts[letterIndex] > letterCounts[letterIndex]) {
33 isValidCombination = false;
34 break; // No need to continue if the combination is invalid
35 }
36 // Calculate score for the current combination
37 currentScore += wordCounts[letterIndex] * score[letterIndex];
38 }
39
40 // If the combination is valid and the score is higher than the maximum found so far, update maxScore
41 if (isValidCombination && maxScore < currentScore) {
42 maxScore = currentScore;
43 }
44 }
45 // Return the maximum score possible with the given words and letters
46 return maxScore;
47 }
48};
49
1// Initializes the letter count array to track the occurrences of each letter.
2const letterCounts: number[] = Array(26).fill(0);
3// Variables to hold the words, letters, and score for global access.
4let words: string[], letters: string[], score: number[];
5// Maximum score initialized to zero.
6let maxScore: number = 0;
7
8// Preprocesses the 'letters' array to populate the 'letterCounts'.
9function preprocessLetters() {
10 for (const letter of letters) {
11 letterCounts[letter.charCodeAt(0) - 'a'.charCodeAt(0)]++;
12 }
13}
14
15// Calculates the maximum score for a combination of words.
16function calculateMaxScore() {
17 const numWords = words.length;
18 // Iterates through all possible combinations of words using bitwise operations.
19 for (let combination = 0; combination < (1 << numWords); ++combination) {
20 const wordCounts = Array(26).fill(0); // Letter counts for the current combination.
21 // Builds the count for the current combination by iterating through each word.
22 for (let wordIndex = 0; wordIndex < numWords; ++wordIndex) {
23 // Checks if the word at 'wordIndex' is included in the current combination.
24 if (combination & (1 << wordIndex)) {
25 // Increments the count for each letter in the word.
26 for (const letter of words[wordIndex]) {
27 wordCounts[letter.charCodeAt(0) - 'a'.charCodeAt(0)]++;
28 }
29 }
30 }
31
32 let isValidCombination: boolean = true; // Flag to check the combination's validity.
33 let currentScore: number = 0; // Score accumulator for the current combination.
34 // Calculating score and checking the validity of the combination.
35 for (let letterIndex = 0; letterIndex < 26; ++letterIndex) {
36 // If the letter count exceeds the available count, mark the combination as invalid.
37 if (wordCounts[letterIndex] > letterCounts[letterIndex]) {
38 isValidCombination = false;
39 break;
40 }
41 // Summing up the score for the current combination.
42 currentScore += wordCounts[letterIndex] * score[letterIndex];
43 }
44
45 // Update maxScore if the current score is greater and the combination is valid.
46 if (isValidCombination && maxScore < currentScore) {
47 maxScore = currentScore;
48 }
49 }
50}
51
52// Function to initiate the calculation of max score by processing the input data.
53function maxScoreWords(wordsInput: string[], lettersInput: string[], scoreInput: number[]): number {
54 words = wordsInput;
55 letters = lettersInput;
56 score = scoreInput;
57 preprocessLetters(); // Fills the letterCounts based on the letters available
58 calculateMaxScore(); // Calculates the score for each possible combination
59 return maxScore; // Returns the highest score found
60}
61
Time and Space Complexity
The given code snippet is a solution to the problem of finding the maximum score from forming words using given letters with each letter having a score.
Time Complexity:
To analyze the time complexity, let's consider n
to be the number of words and l
to be the total number of letters across all words.
- The code uses a bit mask to generate all possible combinations of words, which results in
2^n
combinations as it iterates over a range of size2^n
. - For each combination, it attempts to create a Counter object for the selected words. This operation is linear with respect to the length of the concatenated string of chosen words. In the worst case, this could be
O(l)
when all words are chosen. - The
all
function inside the loop checks if all letters in the current combination are less than or equal to the count of available letters. This runs inO(26)
since there are 26 lowercase English letters, in the worst case where every letter is used. - The sum function, which calculates the total score of current combination of words, will iterate over each character in the concatenated string. This is
O(l)
in the worst case for the same reason as step 2. - Updating the maximum answer
ans
isO(1)
for each of the2^n
combinations.
Combining these steps, the worst-case time complexity is O(2^n * (l + 26 + l + 1))
, which simplifies to O(2^n * l)
as l
dominates the constant 26 and 1.
Space Complexity:
Now, let's look at the space complexity:
- The counter
cnt
stores the frequency of each letter available. This is at mostO(26)
, which is a constantO(1)
because we only have 26 letters. - The
cur
counter inside the loop could store at mostO(26)
entries due to the lowercase letters, so this is alsoO(1)
. - The list
[words[j] for j in range(n) if i >> j & 1]
is ephemeral and its space complexity in terms of the number of characters it can hold is up toO(l)
, when all words are selected. - The combination bitmask takes up to
O(n)
space to store the indices of words.
Considering all the above, the space complexity of the code is dominated by the space needed for the ephemeral list of selected words and the bitmask, and hence it is O(l + n)
.
To summarize, the time complexity is O(2^n * l)
, and the space complexity is O(l + n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following uses divide and conquer strategy?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of
Bitmask and Dynamic Programming Bit manipulation is a crucial aspect of computer programming and one of the most powerful tools for bit manipulation is bitmasks Let's first understand what a bit is A bit is a binary digit It's the smallest piece of data in a computer and can be
Want a Structured Path to Master System Design Too? Donāt Miss This!