<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 {
    using Word = std::array<unsigned char, 26>;

    Word toWord(const std::string& str) const {
        Word word;
        word.fill(0);

        for(const char8_t c : str) {
            ++word[c-'a'];
        }

        return word;
    }

    int calcHelpfulness(const Word& word, const Word& target) const {
        int diff{0}, chars{0};

        for(size_t i{0}; i<26; ++i) {
            if (word[i] > 0 && target[i] > 0) {
                diff += 15;
                chars += std::min(word[i], target[i]);
            }
        }

        return diff + chars;
    }

    bool isEmpty(const Word& w) const {
        return std::all_of(w.cbegin(), w.cend(), [](const int i) { return i <= 0; });
    }

    struct WordHasher {
        size_t operator() (const Word& w) const {
            size_t result{0};
            for(size_t i{0}; i<26; ++i) {
                result += result*10 + w[i];
            }
            return result;
        }
    };


public:
    Solution () {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(0);
    }

    int minStickers(const vector<string>& stickers, const string& target) const {
        std::vector<Word> stckrs;
        stckrs.reserve(stickers.size());
        for(const auto& s : stickers) {
            stckrs.push_back(toWord(s));
        }

        std::queue<std::pair<int, Word>> q;
        q.push({0, toWord(target)});

        std::unordered_set<Word, WordHasher> visited;

        const int max_val{std::numeric_limits<int>::max()};
        int ans{max_val};

        while(!q.empty() && ans == max_val) {
            const auto [curSteps, curTarget] = q.front();
            q.pop();

            if (!visited.contains(curTarget)) {
                visited.insert(curTarget);
            } else { continue; }

            if (isEmpty(curTarget)) {
                ans = curSteps;
                break;
            }

            for(const Word& w : stckrs) {
                if (calcHelpfulness(w, curTarget) <= 0) {
                    continue;
                }

                Word nextTarget{curTarget};
                for(size_t i{0}; i<26; ++i) {
                    nextTarget[i] -= std::min(nextTarget[i], w[i]);
                }

                q.push({1+curSteps, std::move(nextTarget)});
            }
        }

        return ans == max_val ? -1 : ans;
    }
};
63473