**Summary:** continually apply stickers to the target string, attempting to reduce the target string to an empty string through iterative backtracking and recursion with constraint. Keep track of the ongoing minimum amount of stickers needed to construct each reduced target string. ( i.e. `+1`

to the ongoing count `minCnt`

for each sticker which meets the recursive constraint when propagating back up the recursive stack. ) The recursive constraint is NOT met when iterative backtracking results in a target string which CANNOT be further reduced ( see **Base case 2** below for more details ).

**Target reduction formula:**

next target = current target MINUS current sticker

**Use a hash table** to keep track of the minimum count of stickers needed to construct the target string. The key of this hash table is the target string ( along with the various reduced target strings constructed by applying a sticker to the target ). Applying a sticker to a target is the act of removing from the target the common amount of chars between the target and sticker. The value of this hash table is the ongoing minimum count of stickers needed to create the target string.

**Use iterative backtracking** to apply each sticker multiple times and in different orders to try and find new minimums for each new target created by applying each sticker to the current target.

**Use recursion following constraint** which is satisfied if and only if the current sticker applied has reduced the target size. The base case occurs in two different ways, depending on the input.

**Base case 1:** If the set of chars included in the target are a subset of the set of chars from the stickers ( i.e. the stickers can be used in some repetition/combination to completely construct the target ), then the target string will be reduced to an empty string through recursion, and the hash lookup of an empty string returns `0`

. This means that there are `0`

stickers used to create the empty target string `""`

. The `hash`

table is initialized with this entry.

**Base case 2:** If the set of chars included in the target are NOT a subset of the set of chars from the stickers ( i.e. the stickers CANNOT be used to construct the target ), then the recursive constraint will NOT be passed at some point, and the target will NEVER be an empty string. In this case, once iterative backtracking completes, one of the recursive calls will return `-1`

since the target string CANNOT be further reduced at some point. The return value `-1`

is propagated back up the recursive stack and overwrites any and all positive minimum counts calculated so far ( `minCnt`

), since `-1`

is the `min()`

of itself compared to any positive integer tracked by `minCnt`

.

**Solution:** both base case 1 and base case 2 are used to propagate `-1`

or `minCnt`

back up the recursive stack though the `hash`

table once iterative backtracking and constrained recursion complete.

```
class Solution {
private:
vector<int> to_vector(const string &s){
vector<int> res(26, 0);
for (auto&& ch : s) ++res[ch-'a']; // one vector index per char [a:z]
return res;
}
string applySticker(const vector<int>& sticker, const vector<int>& target){
string res{};
for (int i=0; i < target.size(); ++i){ // for each char position
if (target[i] && sticker[i]){
int leftovers=target[i]-sticker[i];
if (leftovers > 0) res+=string(leftovers,i+'a'); // apply char, keep leftovers
}
else if (target[i]) res+=string(target[i],i+'a'); // char NOT applied
}
return res; // alphabetically sorted target MINUS common chars from applying sticker
}
int getMinStickersToCreateTarget(const vector<string>& stickers,
const string& target, unordered_map<string,int>& hash){
if (hash.count(target)) return hash[target]; // base case 1
int minCnt=INT_MAX;
vector<int> vt=to_vector(target);
for (int i=0; i<stickers.size(); ++i){ // iterative backtracking
vector<int> vs=to_vector(stickers[i]);
string next_target=applySticker(vs,vt);
if (next_target.size() < target.size()){ // recursive constraint
int currCnt=getMinStickersToCreateTarget(stickers,next_target,hash);
if (currCnt!=-1) minCnt=min(minCnt,currCnt+1); // +1 sticker applied
}
}
return hash[target]=minCnt==INT_MAX ? -1 : minCnt; // base case 2
}
public:
int minStickers(vector<string>& stickers, string target) {
unordered_map<string,int> hash({{"",0}});
return getMinStickersToCreateTarget(stickers,target,hash);
}
};
```