PUZZLE_LEN = 7


class PuzzleTrie:
    def __init__(self):
        self.cnt = 0
        self.idxes = None
        self.children = {}

    def add_norm_puzzle(self, puzzle_idx: int, norm_puzzle: str) -> None:
        cur = self
        depth = 0
        for i in range(26):
            if (1 << i) & norm_puzzle == 0:
                continue
            depth += 1
            if i not in cur.children:
                cur.children[i] = PuzzleTrie()
            cur = cur.children[i]
        assert depth == PUZZLE_LEN, f"{depth}, {bin(norm_puzzle)}"

        if cur.idxes is None:
            cur.idxes = []
        cur.idxes.append(puzzle_idx)

    def add_norm_word(self, norm_word: int) -> None:
        cur = self
        for i in range(26):
            if (1 << i) & norm_word == 0:
                continue
            if i not in cur.children:
                return
            cur = cur.children[i]
        cur.cnt += 1

    def flatten_counts(self, parent: "Optional[PuzzleTrie]" = None) -> None:
        self.cnt += 0 if not parent else parent.cnt
        for child in self.children.values():
            child.flatten_counts(self)

    def update_puzzle_counts(self, puzzle_counts: List[int]):
        if self.idxes is None:
            for child in self.children.values():
                child.update_puzzle_counts(puzzle_counts)
        else:
            for idx in self.idxes:
                puzzle_counts[idx] += self.cnt

    def to_tuple(self) -> Tuple[int, Optional[List[int]], Dict[int, Any]]:
        children = {}
        for k, v in self.children.items():
            children[k] = v.to_tuple()
        return (self.cnt, self.idxes, children)

    def debug_print(self):
        from pprint import pprint
        pprint(self.to_tuple())



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

        for idx, puzzle in enumerate(puzzles):
            first_letter_idx = ord(puzzle[0]) - ord('a')
            norm_puzzle = self.calc_norm_word(puzzle)
            first_letter_tries[first_letter_idx].add_norm_puzzle(idx, norm_puzzle)

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

            for first_letter_idx in range(26):
                if (1 << first_letter_idx) & norm_word == 0:
                    continue
                first_letter_tries[first_letter_idx].add_norm_word(norm_word)

                if first_letter_idx == 0:
                    print()
                    first_letter_tries[first_letter_idx].debug_print()
                    print()

        ans = [0] * len(puzzles)
        for first_letter_idx, pt in enumerate(first_letter_tries):
            pt.flatten_counts()
            pt.update_puzzle_counts(ans)
        return ans

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