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.

Difficulty: interview

Starter code:

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        

Solutions:
class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        let=Counter(letters)
        sc={}
        for i in range(26):
            sc[chr(i+ord('a'))]=score[i]
        word={}
        for w in words:
            word[w]=Counter(w)
        self.ans=0
        used=[]
        def run(x,cur,let):
            if x==len(words):
                return
            for i in range(x,len(words)):
                if i not in used:
                    tmp=dict(let)
                    bx=True
                    d=0
                    for k,v in word[words[i]].items():
                        if k not in let:
                            bx=False
                            break
                        let[k]-=v
                        d+=(sc[k]*v)
                        if let[k]<0:
                            bx=False
                            break
                    if bx:
                        used.append(i)
                        run(i+1,cur+d,let)
                        if cur+d>self.ans:
                            self.ans=max(self.ans,cur+d)
                        used.pop()
                        let=tmp
                    let=tmp
        run(0,0,let)
        return self.ans

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        # Time O(2^N)
        # Space O(1)
        
        def solve(idx, counter):
            if idx == len(words):
                return 0

            wc = collections.Counter(words[idx])
            if all(counter[key] >= wc[key] for key in wc):
                ans = max(sum(score[ord(c)-ord('a')] for c in words[idx]) + solve(idx+1, counter-wc), solve(idx+1, counter))
            else:
                ans = solve(idx+1, counter) 
                
            return ans
        
        return solve(0, collections.Counter(letters))


from collections import defaultdict, Counter
import copy


class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        def score_of_word(w, score=score):
            ws = 0
            for c in w:
                ws += score[ord(c)-97]
                
            return ws
        
        letter_dict = defaultdict(int)
        for c in letters: letter_dict[c]+=1
            
        def remove_word_from_letter_dict(w, let_dict):
            for c in w:
                let_dict[c] -= 1
                if not let_dict[c]:
                    del let_dict[c]
                    
        def is_word_exist_in_letter_dict(w, let_dict):
            wc = Counter(w)
            for c, f in wc.items():
                if c not in let_dict or let_dict[c] < f:
                    return False
                
            return True
        
        def search_best_score(words, letter_dict, current_score=0):
            best_score = current_score
            for i in range(len(words)):
                w = words[i]
                if is_word_exist_in_letter_dict(w, letter_dict):                    
                    score = current_score + score_of_word(w)
                    copy_letter_dict = copy.deepcopy(letter_dict)
                    remove_word_from_letter_dict(w, copy_letter_dict)
                    score = search_best_score(words[i+1:], copy_letter_dict, score)
                    if score > best_score:
                        best_score = score
                        
            return best_score
        
        return search_best_score(words, letter_dict)

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        lcnt = Counter(letters)
        words = [w for w in words if all(Counter(w)[l] <= lcnt[l] for l in w)]
        al = 'abcdefghijklmnopqrstuvwxyz'
        scores = {w: sum(score[al.index(l)] for l in w) for w in words}
        costs = {w: Counter(w) for w in words}
        score = 0

        for i in range(1, len(words)+1):
            for comb in combinations(words, i):
                if all(sum(costs[w][l] for w in comb) <= lcnt[l] for l in lcnt):
                    score = max(score, sum(scores[w] for w in comb))

        return score

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        let=Counter(letters)
        x=0
        sc={}
        for i in range(26):
            sc[chr(i+ord('a'))]=score[i]
        while x<len(words):
            dic=Counter(words[x])
            bx=True
            for k,v in dic.items():
                if let[k]<v:
                    words.pop(x)
                    bx=False
                    break
            if bx:x+=1
        word={}
        for w in words:
            word[w]=Counter(w)
        self.ans=0
        used=[]
        def run(x,cur,let):
            if x==len(words):
                return
            for i in range(x,len(words)):
                if i not in used:
                    tmp=dict(let)
                    bx=True
                    d=0
                    for k,v in word[words[i]].items():
                        let[k]-=v
                        d+=(sc[k]*v)
                        if let[k]<0:
                            bx=False
                            break
                    if bx:
                        used.append(i)
                        run(i+1,cur+d,let)
                        if cur+d>self.ans:
                            self.ans=max(self.ans,cur+d)
                        used.pop()
                        let=tmp
                    let=tmp
        run(0,0,let)
        return self.ans

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        def letterScore(c):

            return score[ord(c) - ord('a')]

        def helper(i, remaining, scoreSoFar):
            if not remaining or i == len(words):
                return scoreSoFar

            # 1) Skip words[i]
            res = helper(i + 1, remaining, scoreSoFar)

            # 2) Take words[i] if possible
            cw = Counter(words[i])
            if not (cw - remaining):
                res = max(res, helper(i + 1, remaining - cw, scoreSoFar + sum(map(letterScore, words[i]))))

            return res

        return helper(0, Counter(letters), 0)


class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        n = len(words)
        m = len(letters)
        letters = collections.Counter(letters)
        ans = 0
        for i in range(1, n + 1):
            combinations = list(itertools.combinations(words, i))
            for combine in combinations:
                tempScore = self.calculateScore(''.join(combine), letters, score)
                ans = max(tempScore, ans)
        
        
        return ans
    
    def calculateScore(self, s, letters, score):
        counter = collections.Counter(s)
        ans = 0
        for ch in counter:
            if counter[ch] > letters[ch]:
                return float('-inf')
            
            ans += counter[ch] * score[ord(ch) - ord('a')]
            
        return ans


from collections import Counter
class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        letters_dict = Counter(letters)
        res = []
        max_score = 0
        size = len(words)
        def subsets(start, curr):
            res.append(curr)
            for i in range(start, len(words)):
                subsets(i + 1, curr + [words[i]])
        subsets(0, [])
        flag = 0
        for subset in res:
            curr_score = 0
            curr_letters_dict = dict(letters_dict)
            #print(subset)
            for word in subset:
                for char in word:
                    if char in curr_letters_dict and curr_letters_dict[char] > 0:
                        curr_score += score[ord(char) - ord('a')]
                        curr_letters_dict[char] -= 1
                    else:
                        flag = 1
                        break
                if flag:
                    break
            if flag:
                flag = 0
            else:
                max_score = max(max_score, curr_score)
            #print(\"flag and curr_score are:\", flag, curr_score)
        return max_score
            


from collections import defaultdict as dt
def sc(w,z):
    s=0
    for i in w:s+=z[ord(i)-97] 
    return s
def ch(fi,s):
    gi=dt(int)
    for i in s:
        for j in i:
            gi[j]+=1
    for i in gi:
        if gi[i]>fi[i]:return False
    return True
class Solution:
    def maxScoreWords(self, x: List[str], y: List[str], z: List[int]) -> int:       
        fi=dt(int)
        for i in y:fi[i]+=1
        ans=0
        for j in range(1,len(x)+1):
            for i in list(combinations (x,j)):
                ss=0
                if ch(fi,i):
                    for k in i:ss+=sc(k,z)
                    ans=max(ss,ans)
        return ans

from collections import defaultdict as dt
class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        fi = dt(int)
        for i in letters:
            fi[i] += 1
        ans = 0
        for j in range(1,len(words)+1):
            tt = list(combinations(words, j))
            print(tt)
            for i in tt:
                ss = 0
                if ch(fi,i):
                    for k in i:
                        ss+= sc(k,score)
                    ans = max(ss,ans)
        return ans
def sc(w,z):
    s = 0
    for i in w:
        s+=z[ord(i)-97]
    return s

def ch(fi,s):
    gi = dt(int)
    for i in s:
        for j in i:
            gi[j] += 1
    for i in gi:
        if gi[i]>fi[i]: return False
    return True


from copy import deepcopy

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        queue = [[letters, 0, words]]
        visited = []
        max = 0
        
        while len(queue) != 0:
            item = queue.pop(0)
            if (item[0]  in visited):
                continue
            visited.append(item[0])
            
            for word in item[2]:
                lettersCopy = deepcopy(item[0])
                hasEnoughChars = self.hasEnoughChars(lettersCopy, word, score)
                if (hasEnoughChars != - 1 and lettersCopy not in visited):
                    if (item[1]+hasEnoughChars > max):
                        max = item[1]+hasEnoughChars
                    wordsCopy = deepcopy(item[2])
                    wordsCopy.remove(word)
                    queue.append([lettersCopy, item[1]+hasEnoughChars, wordsCopy]) 
        
        return max
                
            
    def charValue(self, letter: str):
        return ord(letter) - 97
    
    def hasEnoughChars(self, letters, word, score):
        sum = 0
        try:
            for x in list(word):
                letters.remove(x)
                sum += score[self.charValue(x)]
        except:
            return -1
            
        return sum

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        res = []
        i = 0
        letters = collections.Counter(letters)
        res = [0]
        self.dfs(i, words, letters, score, 0, res)
        return res[0]
    
    
    def dfs(self, i, words, letters, score, current, res):
        res[0] = max(res[0], current)
        
        for index in range(i, len(words)):
            word = words[index]
            cnt = collections.Counter(word)
            temp = 0
            valid = True
            for ch in cnt:
                if cnt[ch] > letters[ch]:
                    valid = False
                    break
                temp += cnt[ch] * score[ord(ch) - ord('a')]
            
            if not valid:
                continue
            else:   
                for ch in cnt:
                    letters[ch] -= cnt[ch]
                self.dfs(index+1, words, letters, score, current + temp, res)
                for ch in cnt:
                    letters[ch] += cnt[ch]
        return
            
            
                


from collections import Counter
class Solution:
    def subsets(self, words: List[str]) -> List[List[str]]:
        def subsetsHelper(words: List[str]) -> List[List[str]]:
            if len(words) == 0:
                return [[]]
            result = subsetsHelper(words[1:])
            for i in range(len(result)):
               if result[i] != None:
                  l = result[i][:]
                  l.append(words[0])
                  result.append(l)
            return result
        return subsetsHelper(words)
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        def getScores(wordSet:List[str])->int:
            scoreCount = 0
            counter = Counter(letters)
            for word in wordSet:
                for c in word:
                    if not c in counter or counter[c] == 0:
                        return 0
                    counter[c] -= 1
                    scoreCount += score[ord(c)-ord('a')]
            return scoreCount
                
        ans = 0
        for wordSet in self.subsets(words):
            currentScore = getScores(wordSet)
            if currentScore > ans:
                ans = currentScore
        return ans
                
                  
                
                
            


class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        limit = Counter(letters)
        n = len(words)
        subsets = []
        def back(i,curr):
            if i==n:
                subsets.append(curr)
                return
            back(i+1, curr+words[i])
            back(i+1, curr)
        back(0,'')
        print(subsets)
        ans = 0
        
        def findscore(wo):
            freq = Counter(wo)
            currscore = 0
            for c in freq:
                if freq[c]<=limit[c]:
                    currscore+=score[ord(c)-ord('a')]*freq[c]
                else:
                    return 0
            return currscore
            
        for x in subsets:
            ans = max(ans, findscore(x))
        return ans
            


class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        max_score = 0
        word_limits = Counter(letters)
        def helper(curr, chars, curr_words):
            nonlocal max_score
            if curr >= len(words):
                if chars & word_limits == chars:
                    curr_score = sum([chars[c] * score[ord(c) - 97] for c in chars])
                    max_score = max(max_score, curr_score)
                    print(chars)
            else:
                chars += Counter(words[curr])
                helper(curr + 1, chars, curr_words + 1)
                chars -= Counter(words[curr])
                helper(curr + 1, chars, curr_words)         
        helper(0, Counter(), 0)
        return max_score
    
        
        


class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        
        # Time O(2^N)
        # Space O(1)
        
        def solve(idx, counter):
            if idx == len(words):
                return 0

            wc = collections.Counter(words[idx])
            if all(counter[key] >= wc[key] for key in wc):
                ans = max(sum(score[ord(c)-ord('a')] for c in words[idx]) + solve(idx+1, counter-wc), solve(idx+1, counter))
            else:
                ans = solve(idx+1, counter) 
                
            return ans
        
        return solve(0, collections.Counter(letters))

class Solution:
#     def maxScoreWords(self, words, letters, score):
#         self.max_score = 0
#         words_score = [sum(score[ord(c)-ord('a')] for c in word) for word in words]
#         words_counter = [collections.Counter(word) for word in words]
        
#         def dfs(i, curr_score, counter):
#             if curr_score + sum(words_score[i:]) <= self.max_score:
#                 return
#             self.max_score = max(self.max_score, curr_score)
#             for j, wcnt in enumerate(words_counter[i:], i):
#                 if all(n <= counter.get(c,0) for c,n in wcnt.items()):
#                     dfs(j+1, curr_score+words_score[j], counter-wcnt)
        
#         dfs(0, 0, collections.Counter(letters))
#         return self.max_score
    
    
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        def solve(idx, counter):
            if idx == len(words):
                return 0

            wc = collections.Counter(words[idx])
            if all(counter[key] >= wc[key] for key in wc):
                return max(
                    sum(score[ord(c)-ord('a')] for c in words[idx]) + solve(idx+1, counter-wc), 
                    solve(idx+1, counter)
                )
            else:
                return solve(idx+1, counter) 
        
        return solve(0, collections.Counter(letters))

class Solution:
#     def maxScoreWords(self, words, letters, score):
#         self.max_score = 0
#         words_score = [sum(score[ord(c)-ord('a')] for c in word) for word in words]
#         words_counter = [collections.Counter(word) for word in words]
        
#         def dfs(i, curr_score, counter):
#             if curr_score + sum(words_score[i:]) <= self.max_score:
#                 return
#             self.max_score = max(self.max_score, curr_score)
#             for j, wcnt in enumerate(words_counter[i:], i):
#                 if all(n <= counter.get(c,0) for c,n in wcnt.items()):
#                     dfs(j+1, curr_score+words_score[j], counter-wcnt)
        
#         dfs(0, 0, collections.Counter(letters))
#         return self.max_score
    
    
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        def solve(idx, counter):
            if idx == len(words):
                return 0

            wc = collections.Counter(words[idx])
            if all(counter[key] >= wc[key] for key in wc):
                ans = max(sum(score[ord(c)-ord('a')] for c in words[idx]) + solve(idx+1, counter-wc), solve(idx+1, counter))
            else:
                ans = solve(idx+1, counter) 
                
            return ans
        
        return solve(0, collections.Counter(letters))

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        lettersCounter = collections.Counter(letters)
        scoreDict = { letter:score for letter, score in zip('abcdefghijklmnopqrstuvwxyz', score) }
        self.cache = [{} for i in range(len(words))]
        return self.backtracking(words, 0, lettersCounter, scoreDict)

    def backtracking(self, words, cur, remainLC, scoreDict):
        if cur >= len(words):
            return 0
        signature = tuple((key, remainLC[key]) for key in sorted(remainLC))
        if signature in self.cache[cur]:
            return self.cache[cur][signature]

        notChoose = self.backtracking(words, cur+1, remainLC, scoreDict)
        wc = collections.Counter(words[cur])
        if any(remainLC[w] < wc[w] for w in wc.keys()):
            return notChoose
        diff = remainLC - wc
        curScore = sum(scoreDict[ch] for ch in words[cur])
        choose = self.backtracking(words,cur+1, diff, scoreDict)
        ans = max(curScore+choose, notChoose)
        self.cache[cur][signature] = ans
        return ans