<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>

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        stickers = self.removeNonTargetLetters(target, stickers)
        
        N = len(stickers)
        M = 1 << len(target)  # 2^len(target) as the combination of each character {fulfilled vs not}
        
        stickers = [""]+stickers
        dp = [[float('inf') for _ in range(M)] for _ in range(N+1)]
        dp[0][0] = 0   # we need 0 sticker to create an empty target

        for i in range(1, N+1):
            for state in range(M):   # ex:, from b000 to b111 if M = 3
                dp[i][state] = min(dp[i][state], dp[i-1][state])  # if we ignore the sticker[i]
                newState = self.unionState(state, target, stickers[i])
                dp[i][newState] = min(dp[i][newState], dp[i][state]+1)

        return -1 if dp[-1][-1] == float('inf') else dp[-1][-1]

    def removeNonTargetLetters(self, target, stickers):
        t_count = collections.Counter(target)
        A = [collections.Counter(sticker) & t_count
             for sticker in stickers]

        for i in range(len(A) - 1, -1, -1):
            if any(A[i] == A[i] & A[j] for j in range(len(A)) if i != j):
                A.pop(i)

        stickers = ["".join(s_count.elements()) for s_count in A]
        return stickers

    def unionState(self, state, target, sticker):
        n = len(target)
        sticker_count = Counter(sticker)

        for k in range(n):
            # (state >> k) & 1 means extract the k-rightmost bit (1 or 0)
            # ((state >> k) & 1) == 0 means if the kth character of target is not fulfilled yet
            if ((state >> k) & 1) == 0 and sticker_count[target[k]] > 0:
                state += (1 << k)   # Mark the k-th bit as 1 (fulfilled)
                sticker_count[target[k]] -= 1

        return state
31821