Leetcode 1255. Maximum Score Words Formed by Letters

Problem statement

https://leetcode.com/problems/maximum-score-words-formed-by-letters/

Solution

What we need to notice is that there will be 2^m choices at most, where m <= 14, so we can check them all. One option is to use dfs with parameters (F, i) where F is frequencies of letters we have so far and i is index of the next word we want to proceed. Each time we check two options: when we take next word or do not take it. If we have not enough letters, we return immediately. Then we update self.ans. If the next word we want to take has index len(word)` return as well.

Complexity

Time complexity is O(2^m * 26), because we need O(26) operations to update frequencies.

Code

class Solution:
    def maxScoreWords(self, words, letters, S):
        A = [0]*26
        for l in letters:
            A[ord(l) - ord("a")] += 1
        
        def dfs(F, i):
            if any(x > y for x,y in zip(F, A)): return
            self.ans = max(self.ans, sum(x*y for x,y in zip(F, S)))
            if i >= len(words): return
            
            dfs(F, i + 1)
            F2 = F[:]
            for w in words[i]:
                F2[ord(w) - ord("a")] += 1
            dfs(F2, i + 1)
        
        self.ans = 0
        dfs([0]*26, 0)
        return self.ans

Remark

Alternative approach is to use bitmasks with the same complexity