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

/*

stickers:

{w:1, i:1, t:1, h:1}
{e:2, x:1, a:1, m:1, p:1, l:1}
{s:1, c:2, i:1, e:2, n:1}

target:
{t:2, h:2, e:1, a:1}

*/

public:

    int m_size;
    std::unordered_map<std::string, int>* m_cache;
    int (*m_counter)[27];

    int foo(int index, string& target)
    {
        if (m_cache[index].contains(target))
        {
            return m_cache[index][target];
        }
        //cout << "calculating " << target << " on " << index << endl;
        // targetLeft should not be empty
        string targetLeft = target;

        auto t_it = targetLeft.begin();
        int stickerCounter[26];
        for (int i = 0; i < 26; i++)
        {
            stickerCounter[i] = m_counter[index][i];
        }

        while (true)
        {
            if (t_it == targetLeft.end())
            {
                break;
            }
            if (stickerCounter[(*t_it - 'a')]-- > 0)
            {
                t_it = targetLeft.erase(t_it);
            }
            else
            {
                t_it++;
            }
        }

        if (targetLeft.length() == target.length())
        {
            m_cache[index][target] = -1;
            return -1;
        }
        else if (targetLeft.length() == 0)
        {
            m_cache[index][target] = 1;
            return 1;
        }

        int min = -1;
        int minIndex = -1;

        for (int i = 0; i < m_size; i++)
        {
            int current = foo(i, targetLeft);
            if (current > 0)
            {
                if (current < min || min == -1)
                {
                    min = current;
                    minIndex = i;
                }
            }
        }

        if (min > 0) min += 1;
        m_cache[index][target] = min;
        return min;
    }

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

        if (target.empty()) return 0;

        int targetCounter[26];
        for (int i = 0; i < 26; i++) targetCounter[i] = 0;
        for (char& c : target) {
            targetCounter[c - 'a']++;
        }

        for (string& sticker : stickers)
        {
            auto it = sticker.begin();
            while (it != sticker.end())
            {
                if (targetCounter[(*it) - 'a'] == 0) it = sticker.erase(it);
                else it++;
            }
            sort(sticker.begin(), sticker.end());
        }

        m_size = stickers.size();
        m_counter = new int[m_size][27];
        memset(m_counter, 0, m_size * 27 * sizeof(int));
        for (int i = 0; i < m_size; i++)
        {
            string& st = stickers[i];
            for (int j = 0; j < st.length(); j++)
            {
                m_counter[i][st.at(j) - 'a']++;
            }
        }

        for (int i = 0; i < stickers.size(); i++)
        {
            string& sticker = stickers[i];
            for (int j = 0; j < stickers.size(); j++)
            {
                if (i == j || m_counter[j][26]) continue;
                bool covered = true;
                for (char& c : sticker)
                {
                    if (m_counter[j][c - 'a'] < m_counter[i][c - 'a']) {
                        covered = false;
                        break;
                    }
                }
                if (covered)
                {
                    m_counter[i][26] = 1;
                    //cout << sticker << " is covered by " << stickers[j] << endl;
                    break;
                }
            }
        }

        //  remove covered stickers 
        //  1 1 0 1 1 0 1 1 0 1 1 0
        int left = 0;
        int right = m_size - 1;
        while (left < right)
        {
            if (m_counter[left][26] == 0) {
                left++;
                continue;
            }
            if (m_counter[right][26] == 1) {
                right--;
                continue;
            }
            for (int i = 0; i <= 26; i++)
            {
                m_counter[left][i] = m_counter[right][i];
            }
            left++;
            right--;
            m_size--;
        }

        cout << "stickers left: " << m_size << endl;
        string sorted_target = target;
        sort(sorted_target.begin(), sorted_target.end());
        m_cache = new std::unordered_map<std::string, int>[m_size];
        int min = -1;
        int minIndex = -1;
        for (int i = 0; i < m_size; i++)
        {
            int current = foo(i, sorted_target);
            if (current > 0 && (current < min || min < 0))
            {
                min = current;
                minIndex = i;
            }
        }
        return min;
    }
};

140508