<p>You are playing a variation of the game Zuma.</p>

<p>In this variation of Zuma, there is a <strong>single row</strong> of colored balls on a board, where each ball can be colored red <code>&#39;R&#39;</code>, yellow <code>&#39;Y&#39;</code>, blue <code>&#39;B&#39;</code>, green <code>&#39;G&#39;</code>, or white <code>&#39;W&#39;</code>. You also have several colored balls in your hand.</p>

<p>Your goal is to <strong>clear all</strong> of the balls from the board. On each turn:</p>

<ul>
	<li>Pick <strong>any</strong> ball from your hand and insert it in between two balls in the row or on either end of the row.</li>
	<li>If there is a group of <strong>three or more consecutive balls</strong> of the <strong>same color</strong>, remove the group of balls from the board.
	<ul>
		<li>If this removal causes more groups of three or more of the same color to form, then continue removing each group until there are none left.</li>
	</ul>
	</li>
	<li>If there are no more balls on the board, then you win the game.</li>
	<li>Repeat this process until you either win or do not have any more balls in your hand.</li>
</ul>

<p>Given a string <code>board</code>, representing the row of balls on the board, and a string <code>hand</code>, representing the balls in your hand, return <em>the <strong>minimum</strong> number of balls you have to insert to clear all the balls from the board. If you cannot clear all the balls from the board using the balls in your hand, return </em><code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> board = &quot;WRRBBW&quot;, hand = &quot;RB&quot;
<strong>Output:</strong> -1
<strong>Explanation:</strong> It is impossible to clear all the balls. The best you can do is:
- Insert &#39;R&#39; so the board becomes WRR<u>R</u>BBW. W<u>RRR</u>BBW -&gt; WBBW.
- Insert &#39;B&#39; so the board becomes WBB<u>B</u>W. W<u>BBB</u>W -&gt; WW.
There are still balls remaining on the board, and you are out of balls to insert.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> board = &quot;WWRRBBWW&quot;, hand = &quot;WRBRW&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> To make the board empty:
- Insert &#39;R&#39; so the board becomes WWRR<u>R</u>BBWW. WW<u>RRR</u>BBWW -&gt; WWBBWW.
- Insert &#39;B&#39; so the board becomes WWBB<u>B</u>WW. WW<u>BBB</u>WW -&gt; <u>WWWW</u> -&gt; empty.
2 balls from your hand were needed to clear the board.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> board = &quot;G&quot;, hand = &quot;GGGGG&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> To make the board empty:
- Insert &#39;G&#39; so the board becomes G<u>G</u>.
- Insert &#39;G&#39; so the board becomes GG<u>G</u>. <u>GGG</u> -&gt; empty.
2 balls from your hand were needed to clear the board.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= board.length &lt;= 16</code></li>
	<li><code>1 &lt;= hand.length &lt;= 5</code></li>
	<li><code>board</code> and <code>hand</code> consist of the characters <code>&#39;R&#39;</code>, <code>&#39;Y&#39;</code>, <code>&#39;B&#39;</code>, <code>&#39;G&#39;</code>, and <code>&#39;W&#39;</code>.</li>
	<li>The initial row of balls on the board will <strong>not</strong> have any groups of three or more consecutive balls of the same color.</li>
</ul>

#define DEBUG 0
#define UNIFY 1

class Solution {
    using Color = unsigned char;
    static constexpr Color RED = 0;
    static constexpr Color YELLOW = 1;
    static constexpr Color BLUE = 2;
    static constexpr Color GREEN = 3;
    static constexpr Color WHITE = 4;

    static constexpr Color fromLetter(const char c) {
        switch (c) {
        case 'R':
            return RED;
        case 'Y':
            return YELLOW;
        case 'B':
            return BLUE;
        case 'G':
            return GREEN;
        case 'W':
            return WHITE;
        }
        throw std::runtime_error("Should never happen!\n");
    }

    static constexpr char toLetter(const Color c) {
        switch (c) {
        case RED:
            return 'R';
        case YELLOW:
            return 'Y';
        case BLUE:
            return 'B';
        case GREEN:
            return 'G';
        default:
            return 'W';
        }
    }

    using HAND = std::array<int, 5>;

    struct State {
        HAND hand{};
        HAND numBoard{};
        std::vector<std::pair<Color, int>> board;

        [[nodiscard]] std::string getSig() const {

#ifdef UNIFY
            std::array<char, 5> trans{};
            char nextChar = '1';
#endif
            // ok, so we are going to create a trans.

            // we set the hand first.
            std::string out;
            for (const auto& [col, amt] : board) {
#ifdef UNIFY
                if (trans[col] == 0) {
                    trans[col] = nextChar++;
                }
                out.append(amt, trans[col]);
#else
                out.append(amt, toLetter(col));
#endif
            }

#ifdef UNIFY
            for (int i = 0; i < 5; i++) {
                if (trans[i] == 0) {
                    trans[i] = nextChar++;
                }
            }
#endif

            out.append("_");
            for (int i = 0; i < 5; i++) {
#ifdef UNIFY
                out.append(hand[i], trans[i]);
#else
                out.append(hand[i], toLetter(i));
#endif
            }
            return out;
        }

        void simplify() {
            // We here remove all hands that we don't have in the board.

#ifdef DEBUG
            const auto preSig = getSig();
#endif

            bool didSimplify = false;
            for (int i = 0; i < 5; i++) {
                if (numBoard[i] == 0) {
                    if (0 < hand[i] && hand[i] < 3) {
                        didSimplify = true;
                        hand[i] = 0;
                    }
                }
            }

#ifdef DEBUG
            if (didSimplify) {
                std::cout << "SIMPLIFY: From: " << preSig << " to " << getSig()
                          << "\n";
            }
#endif
        }

        [[nodiscard]] bool done() const { return board.empty(); }

        [[nodiscard]] bool impossible() const {
            bool oneHand = false;
            for (int i = 0; i < 5; i++) {
                oneHand = oneHand || (0 < hand[i]);

                if (0 < numBoard[i] && (numBoard[i] + hand[i] < 3))
                    return true;
            }
            return !oneHand;
        }
    };

    using CACHE = std::unordered_map<std::string, int>;

    static int solve(CACHE& cache, const State& state) {
        if (state.done())
            return 0;

        if (state.impossible())
            return -1;

        const auto sig = state.getSig();
        if (auto it = cache.find(sig); it != cache.end()) {
            return it->second;
        }

        // We can also test if hand and board has enough to get to 3, this would
        // allow for ealier termination

        constexpr int SENTINEL = std::numeric_limits<int>::max();
        int ans = SENTINEL;

        const auto N = state.board.size();

        for (int col = 0; col < 5; col++) {
            if (state.hand[col] == 0) {
                continue;
            }

            // we try to put it first or last.
            if (state.board.front().first != col) {
                auto newState = state;
                newState.board.emplace(newState.board.begin(), col, 1);

                newState.hand[col]--;
                newState.numBoard[col]++;

                newState.simplify();
                const auto newAns = solve(cache, newState);
                if (0 <= newAns) {
                    ans = std::min(ans, 1 + newAns);
                }
            }

            //  last.
            if (state.board.back().first != col) {
                auto newState = state;
                newState.board.emplace_back(col, 1);

                newState.hand[col]--;
                newState.numBoard[col]++;

                newState.simplify();
                const auto newAns = solve(cache, newState);
                if (0 <= newAns) {
                    ans = std::min(ans, 1 + newAns);
                }
            }

            // Now for the inbetweens 2s.
            for (int i = 0; i < N; i++) {
                if (state.board[i].first == col || state.board[i].second != 2) {
                    continue;
                }

                auto newState = state;
                newState.board[i].second--;
                newState.board.emplace(newState.board.begin() + i + 1,
                                       newState.board[i].first, 1);
                newState.board.emplace(newState.board.begin() + i + 1, col, 1);

                newState.hand[col]--;
                newState.numBoard[col]++;

                newState.simplify();
                const auto newAns = solve(cache, newState);
                if (0 <= newAns) {
                    ans = std::min(ans, 1 + newAns);
                }
            }

            // ok, now for each that has 2, which we can insert between.
            // we can also see if there is enough to finish everythin on the
            // hand and on the board. if the answer is not enough, then we can
            // exit early
        }

        for (int i = 0; i < N; i++) {
            const auto& [col, amt] = state.board[i];
            const int rem = 3 - amt;

            if (state.hand[col] < rem) {

            } else {
                // ok, we will insert just enough to get 3.
                auto newState = state;
                newState.hand[col] -= rem;

                // We remove the ones which are there.
                newState.numBoard[col] -= amt;

                // ok, now we are simplifying.
                int l = i - 1;
                int r = i + 1;

                // this is the cascade.
                while (0 <= l && r < N) {
                    const auto& [lcol, lamt] = newState.board[l];
                    const auto& [rcol, ramt] = newState.board[r];
                    if (lcol != rcol) {
                        break;
                    }

                    newState.board[l].second += ramt;
                    r++;
                    if (newState.board[l].second < 3) {
                        break;
                    }

                    newState.numBoard[lcol] -= newState.board[l].second;

                    l--;
                }

                newState.board.erase(newState.board.begin() + l + 1,
                                     newState.board.begin() + r);

#ifdef DEBUG
                HAND veri{};
                for (const auto& [hcol, hamt] : newState.board) {
                    veri[hcol] += hamt;
                }
                if (veri != newState.numBoard) {
                    std::cout << "DIFF:\n";
                    std::cout << "VERI: [" << veri[0];
                    for (int i = 1; i < 5; i++) {
                        std::cout << ", " << veri[i];
                    }
                    std::cout << "]\n";

                    std::cout << "STAT: [" << newState.numBoard[0];
                    for (int i = 1; i < 5; i++) {
                        std::cout << ", " << newState.numBoard[i];
                    }
                    std::cout << "]\n";
                }
#endif

                newState.simplify();
                const auto newAns = solve(cache, newState);
                if (0 <= newAns) {
                    ans = std::min(ans, rem + newAns);
                }
            }
        }

        if (ans == SENTINEL)
            ans = -1;

        cache.emplace(sig, ans);
        return ans;
    }

public:
    static int findMinStep(const std::string& board, const std::string& hand) {
        // interesante, molto interesante.

        State root;
        for (const auto c : hand) {
            root.hand[fromLetter(c)]++;
        }

        for (const auto c : board) {
            const auto col = fromLetter(c);
            root.numBoard[col]++;

            if (root.board.empty() || root.board.back().first != col) {
                root.board.emplace_back(col, 1);
            } else {
                root.board.back().second++;
            }
        }
        // we want to simplify as much as possible.
        root.simplify();

        // Ok, now we just need to figure out some smart stuff.
        CACHE cache;
        int sol = solve(cache, root);

#ifdef DEBUG

        /*
        for (const auto& [sig, ans] : cache) {
            std::cout << sig << " = " << ans << "\n";
        }
        */

        std::cout << "Cache cardinality is: " << cache.size() << "\n";
#endif

        return sol;
    }
};
197200