Code

class Solution {
public:
    int findMinStep(string board, string hand) {
        const int n_hand = std::size(hand);

        auto test = [](int mask, int i) { return (mask & (1 << i)) > 0; };
        auto flip = [](int mask, int i) { return mask ^ (1 << i); };

        struct {
            mutable std::unordered_map<std::string, std::optional<int>> f;
        } M;

        auto make_group = [&](const std::string& s) {
            const int ns = std::size(s);
            std::vector<std::pair<char, int>> acc = {};
            for (auto [i, j] = std::pair{0, 0}; j <= ns; ++j) {
                if (j == ns) {
                    if (i < j) {
                        acc.emplace_back(std::pair{s[i], j - 1 - i + 1});
                    }
                }
                else if (s[i] != s[j]) {
                    acc.emplace_back(std::pair{s[i], j - 1- i + 1});
                    std::exchange(i, j);
                }
            }
            return acc;
        };

        auto merge = [&](const std::vector<std::pair<char, int>>& zip) {
            std::string acc = {};
            for (const auto [ch, cnt] : zip) {
                if (cnt < 3) {
                    acc += std::string(cnt, ch);
                }
            }
            return acc;
        };        

        std::function<std::string(const std::string& s)> cancel = [&](const std::string& s) {
            const auto group = make_group(s);
            const bool has_more = std::any_of(std::begin(group), std::end(group), [&](auto && x) {
                return x.second >= 3;
            });

            if (has_more) {
                return cancel(merge(group));
            }
            else {
                return merge(group);
            }
        };

        auto insert_ball = [&](std::string s, int i, char ch){
            s.insert(i, 1, ch);
            return cancel(s);
        };


        auto make_hash = [&](const std::string& s, int mask) {
            std::string used = {};
            for (int i = 0; i < n_hand; ++i) {
                if (not test(mask, i)) {
                    used += hand[i];
                }
            }
            std::sort(std::begin(used), std::end(used));
            return s + "-" + used;
        };


        auto make_bucket = [&](const std::string& s) {
            auto acc = std::unordered_map<char, int>{};
            for (const char ch : s) {
                ++acc[ch];
            }
            return acc;
        };                    

        auto unsolvable = [&](const std::string &s, int mask) {
            const auto bucket_str = make_bucket(s);
            const auto bucket_hand = make_bucket([&]() {
                auto acc = std::string{};
                for (int i = 0; i < n_hand; ++i) {
                    if (not test(mask, i)) {
                        acc += hand[i];
                    }
                }
                return acc;
            }());

            for (const auto [ch, cnt] : bucket_str) {
                if (3 - cnt > 0 and (not bucket_hand.count(ch) or bucket_hand.at(ch) < 3 - cnt)) {
                    return true;
                }
            }
            return false;
        };

        std::function<int(std::string, int)> f = [&, &memo = M.f](std::string s, int mask) {
            const auto hashcode = make_hash(s, mask);
            if (memo[hashcode].has_value()) {
                return memo[hashcode].value();
            }
            else {
                return memo[hashcode].emplace([&] {
                    if (std::empty(s)) {
                        return 0;
                    }
                    else if (__builtin_popcount(mask) == n_hand or unsolvable(s, mask)) {
                        return INT_MAX / 2;
                    }
                    else {
                        int acc = INT_MAX / 2;
                        for (int j = 0; j < n_hand; ++j) {
                            if (not test(mask, j)) {
                                for (int k = 0; k <= std::size(s); ++k) {
                                    acc = std::min(acc, 1 + f(insert_ball(s, k, hand[j]), flip(mask, j)));
                                }
                            }
                        }
                        return acc;
                    }
                }());
            }
        };


        if (const int res = f(board, 0); res >= INT_MAX / 2) {
            return -1;
        }
        else {
            return res;
        }

    }
};