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


/*
1) Optimization: If the target can be spelled out by a group of stickers, at least one of them has to contain character target[0]. So I explicitly require next sticker containing target[0], which significantly reduced the search space.

2) If this sticker didn't contains first character but contains the character after it and it is unique, it will be picked in the future anyway (when that character become the first character). So we won't miss case in such a optimization.

3) Nice optimization! I think the key is you "prioritize" getting rid of target[0] first. And this is totally fine to do b/c in some later iteration the other target[i]'s which you essentially ignored, will make their way to position 0, and then you will handle them appropriately.

bug 1: when you are checking for the emptyness to identify the problem is completed, you have to check for the emptyness of front_str which is a string, and not the front_freq, which is a vector.
bug 2: at the end, return -1, and not return steps
bug 3: steps should be initialized with 0, and not 1
bug 4: the fucked up bug was that I initilized the child with the sticker (almost happened again), instead of with the front as the parent of child (no need to mention these are vector not string)

BUG 5: forgot this condition of --> if (sticker_freq[front_str[0]]==0) continue; (HAPPENED AGAIN)
BUG 6: do freq_to_str correctly, so for that, make you loop from 'a' to 'z', and develop accordingly
BUG 8: push-to-queue and insert-to-hashset happens together with this sequence
BUG 9: stupidliy I wrote int n=qu.empty(), why???!!!
BUG 10: for the first loop do not use 'i' as it will be used later, so just use 'k'
BUG 11: we check count>0 NOT count>1

BUG 7: to check the fist character you have to do it correctly in terms of creating the index --> if(one_sticker_freq[front_str[0]-'a']==0) continue; Happened again, and almost again
BUG 12: the bug i just realized i have had is that this loop can get closed sooner, see the code to undrstand ---> for(int i=0; i<26; ++i)
BUG 13: in the same for loop, note that both left side and right side have [i] --> child[i] -= sticker[i]
BUG 15: keep the function names with str: freqs_to_str() as well as str_to_freqs()
BUG 16: why the fuck i keep writing .inserted(val), instead of insert(val);
BUG 17: FUCK: why did i forget to specify the size of freq in the str_to_freqs method!!!
*/

// note: you need to write both str_to_freqs and freqs_to_str methods
// note: ensure to mention that you go with BFS becuase of getting minium number of stickers
// doubt 1: was very unsure about the steps right after target checking, althought i wrote them correctly but not confidenetly (see the three steps i wrote below)
// doubt 2: was unsure if we return -1 at the end
// doubt 3: initially did not declare the 'level' variable on the top

// ***bug 1: what i thought that the unordered_set can take 'push' method, but it is 'insert' 
// BUG 14: HAPPENED AGAIN and again--> in this line i forgot to declare the string --> string child_str = freqs_to_string(child_freqs);

// solved it correctly, while had the following stupid bugs:
    // bug 0: forgot about --> if(sticker_freq[curr_str[0]-'a']==0) continue;
    // bug 1: when converting str/vec, write correct type
    // bug 2: queue does not have push_back, but it has push
    // bug 3: add type declaration for all new variables
    // bug 4: used : instead of ; within the for-loop
    // bug 5: used 'inserted' instead of 'insert' for visited

// I believe
// TC: O(T * S^T), where 'S' is the number of stickers, and 'T' is length of target
// SC: maximum size of the queue: O(S^T)

// time complexity more info: https://leetcode.com/problems/stickers-to-spell-word/discuss/962702/Java-4-ms-100-BFS-explanation-and-complexity-analysis

    
// vivised is only for optimizaiton
// bug: it is insert, not inserted when inserting to hashset


// remember that you need steps
// initially did not add ++steps, and also return -1
// mistyped ; as :
// forgot to declare curr_str 
// had doubt on what is after child generation
// both sides have []

// **nasty bug: str in the convertor has += operator, and not ==
// bug: forgot to size the freqs vector to 26




// search in the code for all uses of freq, and make sure they all have 's' at the end
// make the 'steps' all plural;
// increment the steps, and return -1, the memoment you establish the for loop

// BUG: fucked up this line by forgetting the right side of it --> vector<int> child_freqs = curr_freqs;
// BUG: totally forgot to return -1
// BUG: in the following, I used front_freq instead of front_str: if(one_sticker_freq[front_str[0]-'a']==0) continue;////


// ***BUG: did not declare string on left side (again) string curr_str = freqs_to_str(curr_freqs);
// ***BUG: used + instead of - here --> child_freqs[i] -= stk_freqs[i];
// ***BUG: this line was wrong: stck_freqs[i]   = stck_freqs[i]<0 ? 0 : stck_freqs[i];

// used the method freqs_to_str without actually define it
// pushed to the qu without declaring it
// ** after generating child_freqs and child_str, I mistakenly worked with sticker, but the sticker was only used to generate the child, and it is the child that we use for queue

// we keep freqs in queue since we need to apply stickers on it, we need string in hashset since this does not need hash function
// be mindful of how you type words without typo
// if(one_sticker[curr_str[0]-'a']==0) continue --> if the target can be spelled out by a group of stickers, then at least one of them must have the first character, so we enforce that to be the first stickers, which significantly reduces the search space
// was very fuzzy in my mind what is remaining after the child is generated which is 3line.
// ***BUG (again): forgot the -'a' --> if(stk_freqs[curr_str[0]-'a']==0) continue;

// it is freqs not freq
// be able to explain why we need to have 'visited' while it is not graph
// it is qu and not queue, do not mix up the name and the type
// **If the target can be spelled out by a group of stickers, at least one of them has to contain character target[0]

// almost forgot to initalize the freqs!

class Solution 
{
    string freqs_to_str(const vector<int>& freqs)
    {
        string str;
        for(char ch='a'; ch<='z'; ++ch) str += string(freqs[ch-'a'], ch);
        return str;
    }
    
    vector<int> str_to_freqs(const string& str)
    {
        vector<int> freqs(26, 0);
        for(char ch : str) ++freqs[ch-'a'];
        return freqs;
    }
    
public:
    int minStickers(vector<string>& stickers, string target) 
    {
        vector<int> target_freqs = str_to_freqs(target); ////
        
        vector<vector<int>> stickers_freqs;
        for(string one_sticker : stickers) stickers_freqs.push_back(str_to_freqs(one_sticker));
        
        queue<vector<int>> qu;
        qu.push(target_freqs);

        unordered_set<string> visited;
        visited.insert(target); //// 
        
        int steps = 0;
        
        while(!qu.empty())
        {
            int K = qu.size();////
            for(int k=0; k<K; ++k)
            {
                vector<int> curr_freqs = qu.front();
                qu.pop();
                
                string curr_str = freqs_to_str(curr_freqs);
                if(curr_str.empty()) return steps;
                
                // just go over the stickers
                /*
                   1) children generatetion
                   2) push to queue
                   3) mark as visited
                */
                for(vector<int> one_sticker_freqs : stickers_freqs)
                {
                    if(one_sticker_freqs[curr_str[0]-'a']==0) continue;////

                    vector<int> child_freqs = curr_freqs;
                    for(int i=0; i<26; ++i)
                    {
                        child_freqs[i] -= one_sticker_freqs[i];
                        child_freqs[i] = (child_freqs[i]<0) ? 0 : child_freqs[i];
                    }
                    string child_str = freqs_to_str(child_freqs);
                    if(visited.count(child_str)>0) continue;////

                    qu.push(child_freqs);
                    visited.insert(child_str);
                }
            }
            ++steps;
        }
        return -1;
    }
};















85483