class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = target.size(), len = stickers.size();
        //dp represents minimum sticker required for current state
        //state is a binary number where each bit represents if corresponding char appears
        vector<int> dp(1 << n, -1);
        dp[0] = 0;
        for(int i = 0; i < 1 << n; ++i)
        {
            if(dp[i] == -1)continue;
            for(auto sticker : stickers)
            {
                int state = i;
                for(int j = 0; j < sticker.size(); ++j)
                {
                    for(int k = 0; k < n; ++k)
                    {
                        //if we have two same chars, two 'a's
                        //if the first 'a' is matched, we don't
                        //want the second 'a' to match the same
                        //position in i again
                        if((state >> k & 1) == 1)continue;
                        if(sticker[j] == target[k])
                        {
                            //if current char c in sticker is matched
                            //it shouldn't match another char in i again,
                            //we just break
                            state |= 1 << k;
                            break;
                        }
                    }
                }
                if(dp[state] == -1 || dp[i] + 1 < dp[state])
                    dp[state] = dp[i] + 1;
            }
        }
        return dp[(1 << n) - 1];
    }
};