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.

Source: leetcode | Difficulty: MEDIUM
Tags: Bit manipulation

String algorithms

Complete search

Dynamic programming

Data structures

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:

		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:

		def letterScore(c):
			return score[ord(c) - ord('a')]

		def helper(i, remaining, scoreSoFar):
			if not remaining or i == len(words):
				return scoreSoFar
			res = helper(i + 1, remaining, scoreSoFar)
			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)
			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)
		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 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:
		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