LC 691: Stickers to Spell Word

# BFS solution where state is the count of characters remaining.


class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        chars_in_target = sorted(list(set(list(target))))
        char_to_idx = {c : i for i, c in enumerate(chars_in_target)}
        n_chars = len(chars_in_target)

        # Reduce word to target chars only, represent as ordered count of chars in target
        # This creates hashable state representations that are efficient to operate on
        def condense(word: str) -> Tuple:
            count_arr = [0 for _ in range(n_chars)]
            for c in word:
                if c not in chars_in_target:
                    continue
                count_arr[char_to_idx[c]] += 1

            return tuple(count_arr)

        # subtract sticker char count from target char count
        def subtract(leftover, sticker):
            return tuple([max(0, leftover[i] - sticker[i]) for i in range(n_chars)])

        # get number of characters a sticker can contribute to the target
        def intersect(a, b):
            return sum([min(a_i, b_i) for a_i, b_i in zip(a, b)])

        processed_stickers = {condense(sticker) for sticker in stickers}
        initial_leftover_count = condense(target)

        # (leftover char count: Tuple, stickers used: int)
        visited = set()
        queue = deque([(initial_leftover_count, 0)])
        visited.add((initial_leftover_count))

        while queue:
            leftover, stickers_used = queue.popleft()
            if sum(leftover) == 0:
                return stickers_used
            to_discard = []
            for sticker in processed_stickers:
                if not intersect(leftover, sticker):
                    to_discard.append(sticker)
                    continue
                new_leftover = subtract(leftover, sticker)
                if new_leftover in visited:
                    continue
                queue.append((new_leftover, stickers_used + 1))

            map(lambda s: processed_stickers.remove(s), to_discard)

        return -1