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, n + 1);
        dp[0] = 0;
        for(int i = 1; i < 1 << n; ++i)
        {
            for(auto sticker : stickers)
            {
                int state = 0;
                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(i >> k & 1 && 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;
                        }
                    }
                }
                dp[i] = min(dp[i], dp[i - state] + 1);
            }
        }
        return dp[(1 << n) - 1] == n + 1? -1: dp[(1 << n) - 1];
    }
};