<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 {
    /*
        thehat -> {a:1, e:1, h:0, t:0 }

        with -> {i:1, h:1, t:1, w:1}
        example -> {a:1, e:2, l:1, m:1, p:1, x:1}
        science -> {e:2, i:1, c:2, n:1, s:1}


        COUNTER EXAMPLE FOR GREEDY 
        target: a:2, b:2, c:2
        [
            a:3,
            c:1, b:1,
            a:1 b:1
        ]
    */
    
    static inline int toIndex(const char c) {
        return (static_cast<int>(c) - static_cast<int>('a'));
    }

    static inline char toChar(const int index) {
        return static_cast<char>(static_cast<int>('a') + index);
    }

    static inline bool isEmpty(const vector<int>& target) {
        for (int i = 0; i < target.size(); i++) {
            if (target[i] > 0) {
                return false;
            }
        }
        return true;
    }

    static inline bool applySticker(const vector<int>& sticker, vector<int>& target) {
        bool applied = false;
        for (int i = 0; i < target.size(); i++) {
            if (!sticker[i] || !target[i]) {
                continue;
            }
            applied = true;
            auto needed = std::min(sticker[i], target[i]);
            target[i] -= needed;
        }
        return applied;
    }

    static inline string serialize(const int pos, const vector<int>& target) {
        ostringstream os;
        os << pos;
        for (int i = 0; i < target.size(); i++) {
            if (target[i]) {
                os << toChar(i);
                os << target[i];
            }
        }
        return os.str();
    }

    inline int getMinStickers(const int pos, vector<vector<int>> &stickers,
        const vector<int>& target, unordered_map<string, int>& mem)
    {
        auto serialized = serialize(pos, target);
        auto it = mem.find(serialized);
        if (it != mem.end()) {
            return it->second;
        }

        auto ret = minStickers(pos, stickers, target, mem);
        mem.insert({serialized, ret});
        return ret;
    }

    int minStickers(const int pos, vector<vector<int>> &stickers,
        const vector<int>& target, unordered_map<string, int>& mem)
    {
        if (pos == stickers.size()) {
            return (isEmpty(target) ? 0 : -1);
        }

        int min_stickers = INT_MAX;
        
        // do not use current
        auto ret = getMinStickers(pos + 1, stickers, target, mem);
        if (ret != -1) {
            min_stickers = std::min(min_stickers, ret);
        }

        int num_applied = 0;
        auto target_copy = target;
        do {
            if (!applySticker(stickers[pos], target_copy)) {
                break;
            }
            ++num_applied;
            ret = getMinStickers(pos + 1, stickers, target_copy, mem);
            if (ret != -1) {
                min_stickers = std::min(min_stickers, num_applied + ret);
            }
        } while (1);

        if (min_stickers == INT_MAX) {
            return -1;
        }

        return min_stickers;
    }

public:
    int minStickers(vector<string>& stickers, string target) {
        vector<int> targetIdx(26, 0);
        for (auto c : target) {
            targetIdx[toIndex(c)]++;
        }

        vector<vector<int>> stickersIdx(stickers.size(), vector<int>(26, 0));
        for (int i = 0; i < stickers.size(); ++i) {
            for (auto c : stickers[i]) {
                stickersIdx[i][toIndex(c)]++;
            }
        }

        unordered_map<string, int> mem;
        return minStickers(0, stickersIdx, targetIdx, mem);
    }
};
426638