<p>We are given <code>n</code> different types of <code>stickers</code>. Each sticker has a lowercase English word on it.</p>

<p>You would like to spell out the given string <code>target</code> by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker.</p>

<p>Return <em>the minimum number of stickers that you need to spell out </em><code>target</code>. If the task is impossible, return <code>-1</code>.</p>

<p><strong>Note:</strong> In all test cases, all words were chosen randomly from the <code>1000</code> most common US English words, and <code>target</code> was chosen as a concatenation of two random words.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> stickers = [&quot;with&quot;,&quot;example&quot;,&quot;science&quot;], target = &quot;thehat&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong>
We can use 2 &quot;with&quot; stickers, and 1 &quot;example&quot; sticker.
After cutting and rearrange the letters of those stickers, we can form the target &quot;thehat&quot;.
Also, this is the minimum number of stickers necessary to form the target string.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> stickers = [&quot;notice&quot;,&quot;possible&quot;], target = &quot;basicbasic&quot;
<strong>Output:</strong> -1
Explanation:
We cannot form the target &quot;basicbasic&quot; from cutting letters from the given stickers.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == stickers.length</code></li>
	<li><code>1 &lt;= n &lt;= 50</code></li>
	<li><code>1 &lt;= stickers[i].length &lt;= 10</code></li>
	<li><code>1 &lt;= target.length &lt;= 15</code></li>
	<li><code>stickers[i]</code> and <code>target</code> consist of lowercase English letters.</li>
</ul>

"""
___
Goal:
___

return min # stickers to spell out target

____
Examples:
____

Input: stickers = ["with","example","science"], target = "thehat"
Output: 3

Input: stickers = ["notice","possible"], target = "basicbasic"
Output: -1



___
Assumptions:
___

1. given stickers: 1 <= len(stickers[i]) <= 10, 1 <= len(stickers) <= 50

2. each sticker has a lowercase english word on it

3. stickers are fungible, as you can use unlimited per unique sticker

4. you can cut individual letters from stickers
    - i.e. you can extract their characters to build char_freq map


___
PsuedoCode:
___

1. if not all the characters present in target are in any of the stickers, we return false


State:
    - freq_bank: encapsulates the characters we can currently use
    - chars_matched:
    - word_index: tells us which word to inspect next
    - curr_stickers
    - STOP STATE:
        - chars_matched == len(target)
        - word_index == len(stickers)
        - min_stickers > curr_stickers

Traversal:
    - we either use the same word, skip the current word, or go to next
    - 


"""


class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        
        characters = set()

        for sticker in stickers:
            characters |= set(sticker)
        
        if set(target) & characters != set(target):
            return -1

        char_bank = {}
        memo = {}

        def update_state(sticker: str, remainder: str):

            for c in sticker:
                char_bank[c] = char_bank.get(c, 0) + 1
            
            result, used = '', ''

            for c in remainder:
                if c in char_bank:
                    char_bank[c] -= 1
                    if not char_bank[c]:
                        char_bank.pop(c)
                    used += c
                else:
                    result += c

            return result, used

        def reset_state(sticker: str, used: str):
            for c in used:
                    char_bank[c] = char_bank.get(c, 0) + 1

            for c in sticker:
                char_bank[c] = char_bank.get(c, 0) - 1
                if not char_bank[c]:
                        char_bank.pop(c)
            

        def dfs(sticker_idx: int, remainder: str):
            
            if not remainder:
                return 0
            elif sticker_idx == len(stickers):
                return float('inf')
            elif (sticker_idx, remainder) in memo:
                return memo[(sticker_idx, remainder)]
                
            # don't take the sticker
            output = dfs(sticker_idx + 1, remainder)
            
            # take the sticker
            if can_take_sticker := set(stickers[sticker_idx]) & set(remainder):
                
                result, used = update_state(stickers[sticker_idx], remainder)

                output = min(output, 1 + dfs(sticker_idx, result))

                reset_state(stickers[sticker_idx], used)

            memo[(sticker_idx, remainder)] = output
            return output



        return dfs(0, target)

89808