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

public:
   int minStickers(vector<string>& stickers, string target) {

         int targetMask = (1 << target.length()) - 1;
         unordered_set<int> visisted;

        vector<int> targetVec(26, 0);

        GenerateByStr(target, targetVec, vector<int>());
        vector<vector<int>>  stickersVec;
        for (int i = 0; i < stickers.size(); i++)
        {
            vector<int> tmpVec(26, 0);
            if (GenerateByStr(stickers[i], tmpVec, targetVec))
            {
                stickersVec.emplace_back(tmpVec);
            }
        }

        int length = 0;
        queue<int> maskq;
        maskq.push(0);
        visisted.insert(0);

        while (!maskq.empty())
        {

            int size = maskq.size();
            for (int i = 0; i < size; i++)
            {
                int mask = maskq.front();
                maskq.pop();
                
                    if (mask == targetMask)
                    {
                        return length;
                    }
   
                for (int idx = 0; idx < stickersVec.size(); idx++)
                {
                    auto freq = stickersVec[idx];
                    int newmask = mask;
                    for (int i = 0; i < target.size(); i++)
                    {
                        // this means we need one 
                        if (((1 << i) & mask) == 0 && freq[target[i] - 'a'] > 0)
                        {
                            newmask |= (1 << i);
                            freq[target[i] - 'a']--;
                        }
                    }

                    
                    if (visisted.find(newmask) == visisted.end())
                    {
                        visisted.insert(newmask);
                        maskq.push(newmask);
                    }
                }
            }

            length++;
        }

        return -1;


        //auto ans = DPSHelper(0, target, stickersVec);

        //return ans == 1e9 ? -1 : ans;
    }
  bool GenerateByStr(const std::string& p_string, vector<int>& ans, const vector<int>& target)
    {
        bool added = false;
        for (int i = 0; i < p_string.size(); i++)
        {
            int idx = p_string[i] - 'a';
            if (target.empty() || target[idx] > 0)
            {
                ++ans[idx];
                added = true;
            }

        }

        return added;
    }
    /*int DPSHelper(int mask, const string& target, vector<vector<int>>& stickersVec)
    {
        if (mask == ((1 << target.length()) - 1))
        {
            return 0;
        }

        if (m_dpresult[mask] != -1)
        {
            return m_dpresult[mask];
        }

        int ans = 1e9;
        for (int idx = 0; idx < stickersVec.size(); idx++)
        {
            auto freq = stickersVec[idx];

            int newmask = 0;
            for (int i = 0; i < target.size(); i++)
            {
                // this means we need one 
                if (((1 << i) & mask) == 0 && freq[target[i] - 'a'] > 0)
                {
                    newmask |= (1 << i);
                    freq[target[i] - 'a']--;
                }
            }

            if (newmask != 0)
            {
                ans = std::min(ans, 1 + DPSHelper(newmask | mask, target, stickersVec));
            }



        }

        m_dpresult[mask] = ans;

        return m_dpresult[mask];
    }*/


};
283573