Given a list of words, list of&nbsp; single&nbsp;letters (might be repeating)&nbsp;and score&nbsp;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&nbsp;or more times).

It is not necessary to use all characters in letters and each letter can only be used once. Score of letters&nbsp;'a', 'b', 'c', ... ,'z' is given by&nbsp;score[0], score[1], ... , score[25] respectively.

&nbsp;
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.

&nbsp;
Constraints:


	1 &lt;= words.length &lt;= 14
	1 &lt;= words[i].length &lt;= 15
	1 &lt;= letters.length &lt;= 100
	letters[i].length == 1
	score.length ==&nbsp;26
	0 &lt;= score[i] &lt;= 10
	words[i], letters[i]&nbsp;contains only lower case English letters.


from itertools import combinations 

class Solution:
    def createNewWord(self, wordList) : 
        ans = ''
        for word in wordList :
            ans += word 
        
        charList = [i for i in ans]
        return charList 
    
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        score_dict = {}
        ord_a = 97 
        for i in range(len(score)) : 
            score_dict[chr(ord_a + i)] = score[i]
            
        max_count, sum_list, to_remove = 0, [], []
        for word in words : 
            char_list = [i for i in word]
            max_num = 0
            for char in set(char_list) : 
                if char_list.count(char) > letters.count(char) : 
                    max_num = 0
                    to_remove.append(word)
                    break 
                else : 
                    max_num += score_dict[char]*char_list.count(char)

            if max_num > 0 :
                sum_list.append(max_num)
        
            if max_num > max_count : 
                max_count = max_num 
        
        new_word = [i for i in words if i not in to_remove]
        # print(new_word)
        for i in range(2, len(sum_list)+1) :
            comb = combinations(new_word, i)
            for c in comb : 
                combinedWord = self.createNewWord(c)
                totalNum = 0
                for char in set(combinedWord) : 
                    if combinedWord.count(char) > letters.count(char) : 
                        totalNum = 0
                        break 
                    else : 
                        totalNum += score_dict[char]*combinedWord.count(char)
                if totalNum > max_count : 
                    max_count = totalNum 
                    
        return max_count 
class Solution {
    int[] memo;
    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        memo = new int[words.length];
        Arrays.fill(memo,-1);
        HashMap<Character,Integer> hm = new HashMap<>();
        for(char c : letters){
            int t = hm.getOrDefault(c,0);
            t++;
            hm.put(c,t);
        }
        //return dp(words,hm,score,0,0);
        int res = dp(words,hm,score,0,0);
        //for(int i : memo) System.out.println(i);
        return res;
    }

    public int dp(String[] words, Map<Character,Integer> hm, int[] score, int index, int cs){//cs-current Score
        if(index==words.length) return cs;
        if(memo[index]!=-1) return memo[index];
        HashMap<Character,Integer> temp = new HashMap<>(hm);
        int tcs=cs; //tcs = temporory current score

        for(char c : words[index].toCharArray()){
            int t = temp.getOrDefault(c,0);
            t--;
            if(t<0){
                return dp(words,hm,score,index+1,cs);
                // memo[index] = dp(words,hm,score,index+1,cs);
                // return memo[index];
            }
            tcs+=score[c-'a'];
            temp.put(c,t);
        }
        return Math.max(dp(words,hm,score,index+1,cs),dp(words,temp,score,index+1,tcs));
        // memo[index] = Math.max(dp(words,hm,score,index+1,cs),dp(words,temp,score,index+1,tcs));
        // return memo[index];
    }
}
class Solution {
public:
    int calc(vector<string>& words,map<char,int>&m,vector<int>& score,int i){ 
        int maxi=0;
        if(i==words.size())
            return 0;
        map<char,int>m1=m;//Creating a duplicate in case the given word does not satisfy our answer
        int c=0;//Store the score
        for(int j=0;j<words[i].length();j++){
            if(m1.find(words[i][j])==m1.end()||m1[words[i][j]]==0){//If frequency of the letter reduces to zero or that letter is not present in our hashMap            
                c=-1;
                break;
            }
            c+=score[words[i][j]-'a'];
            m1[words[i][j]]--;
        }        
        if(c!=-1)           
          maxi=c+(calc(words,m1,score,i+1));//We are considering the current word and adding it to our answer
        return max(maxi,calc(words,m,score,i+1));//FInding tha maximum between when we consider the current word and when we DONT consider current word
        
}
    int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
        map<char,int>m;       
        for(auto i:letters)
            m[i]++;
        return calc(words,m,score,0);   
    }
};
var maxScoreWords = function(words, letters, score) {
    // unique chars
    let set = new Set();
    for (let w of words)
        for (let c of w)
            set.add(c)

    // score of unique chars
    let map = new Map();
    for (let c of set)
        map.set(c, score[c.charCodeAt() - 'a'.charCodeAt()])

    // letter count
    let map_letters = new Map();
    for (let c of letters)
        map_letters.set(c, map_letters.has(c) ? map_letters.get(c) + 1 : 1);

    // score of words
    let SW = [];
    for (let w of words) {
        let s = 0;
        for (let c of w)
            s += map.get(c)
        SW.push(s)
    }

    const sortStr = (s) => s.split("").sort().join("")
    const combineStrings_fromArrayAndIndexes = (A, I) => I.reduce((s, i) => (s + A[i]), '')
    const getFreqMapFromStr = (s) => s.split("").reduce((m, c) => (m.set(c, m.has(c) ? m.get(c) + 1 : 1), m), new Map())
    const isMapSubOfAnotherMap = (m1, m2) => {
        for (let [c, count] of m1)
            if (!m2.has(c) || count > m2.get(c))
                return false
        return true
    }

    let max1 = -Infinity;
    const takeOrNot = (i, take, indexes, A, n) => {
        if (i === n) {
            if (isMapSubOfAnotherMap(
                    getFreqMapFromStr(
                        combineStrings_fromArrayAndIndexes(words, indexes)
                    ),
                    map_letters
                )) {
                let mm = indexes.reduce((sum, i) => sum + SW[i], 0)
                max1 = Math.max(max1, mm);
            }
            return
        }
        takeOrNot(i + 1, take, indexes, A, n)
        takeOrNot(i + 1, take, [...indexes, i], A, n);
    }
    takeOrNot(0, true, [], SW, SW.length);
    return max1;
};
Maximum Score Words Formed by Letters