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

    struct CharComposition{

        int count[26];

        CharComposition():count{}{}
    };

    unordered_map<string, int > dp;


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

        vector<vector<int> > charCountOfSticker( stickers.size(), vector<int>( 26, 0 ) );
        vector<vector<int> > stickerContainingChar( 26, vector<int>() );
        
        for( int i = 0 ; i < stickers.size() ; i++ ){

            for( auto ch : stickers[i] )
                charCountOfSticker[i][ ch - 'a' ]++;

            for( int j = 0 ; j < 26 ; j++ ){

                if( charCountOfSticker[i][ j ] > 0 )
                    stickerContainingChar[j].push_back( i );
            }
        }

        dp[ "" ] = 0;

        vector<int> charToBeMatched( 26, 0 );

        for( auto & ch : target ){
            charToBeMatched[ ch - 'a' ]++;
        }

        int res = topDown( charToBeMatched, stickerContainingChar, charCountOfSticker );

        return res == INT_MAX ? -1 : res;
        
    }


    long long int topDown( vector<int> charToBeMatched, const vector<vector<int> > & stickerContainingChar, const vector<vector<int> > & charCountOfSticker   ){

        long long int res = INT_MAX;

        string token;

        for( int i = 0 ; i < 26 ; i++ ){
            if( charToBeMatched[i] > 0 ){

                token.push_back( 'a' + i );
                token.insert( token.size(), to_string( charToBeMatched[i] ) );
            }
        }

        if( dp.contains( token ) )
            return dp[ token ];

        for( int i = 0 ; i < 26 ; i++ ){

            if( charToBeMatched[i] > 0 ){

                for( auto j : stickerContainingChar[i] ){

                    for( int k = 0 ; k < 26 ; k++ ){
                        charToBeMatched[k] -= charCountOfSticker[j][k];
                    }

                    res = min( res, 1 + topDown( charToBeMatched, stickerContainingChar, charCountOfSticker ) );

                    for( int k = 0 ; k < 26 ; k++ ){
                        charToBeMatched[k] += charCountOfSticker[j][k];
                    }
                }
            }
        }

        dp[token] = res;

        return res;

    }


};















// class Solution {

//     struct CharComposition{

//         int count[26];

//         CharComposition():count{}{}
//     };

//     unordered_map<string, int > dp;


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


//         vector<vector<int>> charToWords( 26, vector<int>() );

//         vector<CharComposition> wordToComposition( stickers.size(), CharComposition() );

//         for( int i = 0 ; i < stickers.size() ; i++ ){

//             for( auto c : stickers[i] ){

//                 wordToComposition[i].count[ c - 'a' ]++;

//             }

//             for( int j = 0 ; j < 26 ; j++ ){

//                 if( wordToComposition[i].count[ j ] > 0 )
//                     charToWords[j].push_back( i );
//             }

//         }

//         CharComposition targetComposition;

//         for( char & c : target ){

//             targetComposition.count[ c - 'a' ]++;
//         }

//         int res = TopDown( targetComposition, charToWords, wordToComposition );


//         return res == INT_MAX ? -1 : res ;

        
//     }


//     long long int TopDown( CharComposition target, vector<vector<int>>& charToWords, vector<CharComposition>& wordToComposition ){

//         long long int res = INT_MAX, count;


//         string token;

//         for( int i = 0 ; i < 26 ; i++ ){

//             if( target.count[i] > 0 ){
//                 token.push_back( 'a' + i );
//                 token.insert( token.size(), to_string( target.count[i] ) );
                
//             }
//         }

//         if( token.empty() )
//             return 0;

//         if( dp.find( token ) != dp.end()  )
//             return dp[token];

//         for( int i = 0 ; i < 26 ; i++  ){

//             if( target.count[i] > 0 ){

//                 for( int j : charToWords[i] ){

//                     // count = target.count[i] / wordToComposition[j].count[i] + ( target.count[i] % wordToComposition[j].count[i] > 0 );

//                     CharComposition childTarget = target;

//                     for( int k = 0 ; k < 26 ; k++ ){

//                         childTarget.count[k] -= wordToComposition[j].count[k];

//                         if( childTarget.count[k] < 0 ) childTarget.count[k] = 0;

//                     }

//                     res = min( res, 1 + TopDown( childTarget, charToWords, wordToComposition ) );

//                 }

//             }

//         }


//         dp[ token ] = res;

//         return res;


//     }


// };
399126