• Posts

Problem 1255 Maximum Score Words Formed by Letters

Problem Statement

Link - Problem 1255

Question

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.

Solution

class Solution {
public:
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        vector<int> count(26, 0);
        vector<int> lettersCount(26, 0);
        for(auto &c : letters){
            count[c - 'a']++;
        }
        int ans = 0;
        backtracking(words, score, count, lettersCount, 0, 0, ans);
        return ans;
    }
    void backtracking(vector<string>& words, vector<int>& score, vector<int>& count, vector<int>& lettersCount, int pos, int temp, int &ans){
        for(int i = 0; i < 26; i++){
            if(lettersCount[i] > count[i])
                return;
        }
        ans = max(ans, temp);
        for(int i = pos; i < words.size(); i++){
            for(auto& c : words[i]){
                lettersCount[c - 'a']++;
                temp+=score[c - 'a'];
            }
            backtracking(words, score, count, lettersCount, i + 1, temp, ans);
            for(auto& c : words[i]){
                lettersCount[c - 'a']--;
                temp-=score[c - 'a'];
            }
        }
    }
};

Complexity Analysis

| Algorithm                                               | Time Complexity  | Space Complexity |
| ------------------------------------------------------- | ---------------- | ---------------- |
| Backtracking for String Scoring with Depth-First Search | O((2^n) 26m + n) | O(n)             |

Explanation

Intial Thoughts

• Treat each word as a different option in a multiple choice problem, look for all different possible word combinations, - Consider using backtracking to automatically traverse through all the word combinations, - It is also crucial to determine all other available letters which are in our letter bank after selecting some words,
  • Each letter can only be used once when finding possible word combinations and check for cases where word letters may not exist in our letter bank

Intuitive Analysis

• Focus on considering that once one selects a word it then modifies the possible letter bank we can then select from going forward.
  • Think of it as either selecting or skipping word possibilities from within our word database with the hope to maximize score we are trying to find. - Break the letters bank available based on how much we are iteratively willing to spend and backtrack over given words, - A good strategy also involves evaluating what the letters we cant form actually cost you.

1. Intuition

• The problem can be solved using backtracking, which is a form of recursion.
• The key insight is to try all possible combinations of words and keep track of the maximum score.
• We need to keep track of the count of each letter in the letters array and the current word being processed.
• We also need to keep track of the temporary score for the current combination of words.
• The backtracking approach allows us to explore all possible combinations of words and find the maximum score.
• The time complexity of this approach is O(2^n * m), where n is the number of words and m is the maximum length of a word.
• The space complexity is O(n * m), where n is the number of words and m is the maximum length of a word.

2. Implementation

• We start by initializing the count array to keep track of the count of each letter in the letters array.
• We then call the backtracking function with the initial position, temporary score, and answer.
• In the backtracking function, we first check if the current combination of words is valid by checking if the count of each letter in the lettersCount array is less than or equal to the count in the count array.
• If the current combination is valid, we update the answer with the maximum score.
• We then try to add each word to the current combination and recursively call the backtracking function.
• After trying all words, we backtrack by removing the last word from the current combination and restoring the count of each letter in the lettersCount array.
• We use lettersCount[c - 'a']++ to increment the count of each letter in the lettersCount array and temp += score[c - 'a'] to update the temporary score.

Complexity Analysis

Time Complexity:

• The time complexity is dominated by the recursive call in the backtracking function, which is called for each word (backtracking(words, score, count, lettersCount, i + 1, temp, ans)). This results in 2^n recursive calls, where n is the number of words.
• Inside each recursive call, the algorithm iterates over the characters of the current word (for(auto& c : words[i])), and also checks the count of letters (for(int i = 0; i < 26; i++)), which results in an additional O(m * 26) time complexity, where m is the maximum length of the word.
• Overall, the time complexity can be expressed as O(2^n _ m _ 26 + n), where the dominant term is the recursive call.

Space Complexity:

• The space complexity is dominated by the recursion stack (backtracking(words, score, count, lettersCount, i + 1, temp, ans)), which can go up to n levels deep, where n is the number of words.
• Additionally, the algorithm uses several arrays to keep track of the count of letters and the score for each letter, which results in a space complexity of O(26) due to the fixed size arrays (vector<int> count(26, 0) and vector<int> lettersCount(26, 0)).
• However, since the space complexity of the array is constant, it does not affect the overall space complexity, which is therefore O(n).

Footnote

This question is rated as Hard difficulty.

Hints

Note that words.length is small. This means you can iterate over every subset of words (2^N).

Similar Questions: