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

// BFS
// edge = remove letter until target = ""
// class Solution {
// public:
//     int minStickers(vector<string>& stickers, string& target) {
//         int n = stickers.size();
//         unordered_set<string> visited;

//         vector<vector<int>> s_frequencies(n, vector<int>(26, 0));
//         for (int i = 0; i < n; ++i)
//             for (char c : stickers[i])
//                 s_frequencies[i][c-'a']++;
        
//         vector<int> t_frequency(26, 0);
//         for (char c : target)
//             t_frequency[c-'a']++;

//         queue<vector<int>> q;
//         q.push(t_frequency);

//         int res = 0;
//         while (!q.empty()) {
//             int sz = q.size();
//             for (int k = 0; k < sz; k++) {
//                 auto t_freq = q.front(); q.pop();

//                 // Reconstruct string based on frequency
//                 string t_str;
//                 for (int i = 0; i < 26; ++i)
//                     if (t_freq[i] > 0)
//                         t_str += string(t_freq[i], i);

//                 if (t_str == "") 
//                     return res;

//                 if (visited.count(t_str)) 
//                     continue;
//                 visited.insert(t_str);

//                 char seeking = t_str[0];
//                 for (auto& s_freq : s_frequencies) {
//                     if (s_freq[seeking] > 0) {
//                         vector<int> remain = t_freq;                    
//                         for (int i = 0; i < 26; ++i)
//                             remain[i] -= s_freq[i];
//                         q.push(remain);
//                     }
//                 }
//             }
//             res++;
//         }
//         return -1;
//     }
// };

// BIT DP
// class Solution {
// public:
//     int n, target_len;
//     vector<int> dp;
//     vector<vector<int>> counts;
    
//     vector<string> stickers;
//     string target;

//     int minStickers(vector<string>& stickers, string target) {
//         this->stickers = stickers;
//         this->target = target;

//         n = stickers.size(), target_len = target.size();
//         dp = vector<int>(1 << target_len, -1); // 2^n
//         counts = vector<vector<int>>(n, vector<int>(26, 0));

//         for (int i = 0; i < n; i++) {
//             for (char ch : stickers[i]) {
//                 counts[i][ch-'a']++;
//             }
//         }

//         int sol = rec(0);
//         if (sol == target_len+1)
//             return -1;
//         return sol;
//     }

//     // mask: 1s = already matched chars
//     int rec(int mask) {
//         // all 1s = all matched
//         if (mask == (1<<target_len)-1) 
//             return 0;
//         if (dp[mask] != -1) 
//             return dp[mask];

//         int min_stickers = target_len+1; // essentially infinity -> can't take this many stickers
//         for (int i=0; i<n; i++) {
//             vector<int> stick_cnt = counts[i];

//             int newmask = 0;
//             for (int j=0; j<target_len; j++) {
//                 // if jth bit (from right) = 0 -> not matched
//                 if (!((1<<j)&mask)) {
//                     // set (match) if present in current sticker
//                     if (stick_cnt[target[j]-'a'] > 0) {
//                         stick_cnt[target[j]-'a']--;
//                         newmask |= (1<<j);
//                     }
//                 }
//             }
//             // take this sticker only if it contributes anything to the mask
//             if (newmask != 0) 
//                 min_stickers = min(min_stickers, 1+rec(mask|newmask));
//         }
//         return dp[mask] = min_stickers;
//     }
// };

// MAP OF REMAINING IN TARGET
class Solution {
public:
    int n, target_len;
    unordered_map<string, int> dp;
    vector<vector<int>> counts;
    vector<string> stickers;
    string target;

    int minStickers(vector<string>& stickers, string target) {
        this->stickers = stickers;
        this->target = target;

        n = stickers.size(), target_len = target.size();
        counts = vector<vector<int>>(n, vector<int>(26, 0));

        for (int i = 0; i < n; i++) {
            for (char ch : stickers[i]) {
                counts[i][ch-'a']++;
            }
        }

        int sol = rec(target);
        if (sol == target_len+1)
            return -1;
        return sol;
    }

    int rec(string target) {
        if (target.empty()) 
            return 0;
        if (dp.find(target) != dp.end()) 
            return dp[target];

        int min_stickers = target_len+1; // essentially infinity -> can't take this many stickers
        for (int i=0; i<n; i++) {
            vector<int> stick_cnt = counts[i];
            if (stick_cnt[target[0]-'a'] == 0) {
                continue;
            }

            vector<int> target_cnt(26, 0);
            for (char ch : target) {
                target_cnt[ch-'a']++;
            }

            string new_target;
            for (int j = 0; j < 26; ++j) {
                int diff = target_cnt[j] - stick_cnt[j];
                new_target += string(max(diff, 0), 'a' + j);
            }
            
            // otherwise, didn't sub any chars
            if (new_target.size() < target.size()) {
                min_stickers = min(min_stickers, 1+rec(new_target));
            }
        }
        return dp[target] = min_stickers;
    }
};
90986