PUZZLE_LEN = 7

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        norm_word_counters = [Counter() for _ in range(26)]

        for word in words:
            norm_word = self.calc_norm_word(word)
            if bin(norm_word).count("1") > PUZZLE_LEN:
                continue

            for fli in range(26):  # First letter index
                if (1 << fli) & norm_word == 0:
                    continue
                norm_word_counters[fli][norm_word] += 1

        ans = [0] * len(puzzles)
        for pi, puzzle in enumerate(puzzles):
            fli = ord(puzzle[0]) - ord('a')
            normed_letters = [(1 << (ord(c) - ord('a'))) for c in puzzle]

            for subset in self.powerset(normed_letters):
                norm_puzzle = sum(subset)
                ans[pi] += norm_word_counters[fli][norm_puzzle]
        return ans

    def calc_norm_word(self, word: str) -> int:
        normed = 0
        for c in word:
            normed |= 1 << (ord(c) - ord('a'))
        return normed

    def powerset(self, elems):
        return chain.from_iterable(
            combinations(elems, r) for r in range(1, len(elems)+1)
        )