<p>We can scramble a string s to get a string t using the following algorithm:</p>

<ol>
	<li>If the length of the string is 1, stop.</li>
	<li>If the length of the string is &gt; 1, do the following:
	<ul>
		<li>Split the string into two non-empty substrings at a random index, i.e., if the string is <code>s</code>, divide it to <code>x</code> and <code>y</code> where <code>s = x + y</code>.</li>
		<li><strong>Randomly</strong>&nbsp;decide to swap the two substrings or to keep them in the same order. i.e., after this step, <code>s</code> may become <code>s = x + y</code> or <code>s = y + x</code>.</li>
		<li>Apply step 1 recursively on each of the two substrings <code>x</code> and <code>y</code>.</li>
	</ul>
	</li>
</ol>

<p>Given two strings <code>s1</code> and <code>s2</code> of <strong>the same length</strong>, return <code>true</code> if <code>s2</code> is a scrambled string of <code>s1</code>, otherwise, return <code>false</code>.</p>

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

<pre>
<strong>Input:</strong> s1 = &quot;great&quot;, s2 = &quot;rgeat&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> One possible scenario applied on s1 is:
&quot;great&quot; --&gt; &quot;gr/eat&quot; // divide at random index.
&quot;gr/eat&quot; --&gt; &quot;gr/eat&quot; // random decision is not to swap the two substrings and keep them in order.
&quot;gr/eat&quot; --&gt; &quot;g/r / e/at&quot; // apply the same algorithm recursively on both substrings. divide at random index each of them.
&quot;g/r / e/at&quot; --&gt; &quot;r/g / e/at&quot; // random decision was to swap the first substring and to keep the second substring in the same order.
&quot;r/g / e/at&quot; --&gt; &quot;r/g / e/ a/t&quot; // again apply the algorithm recursively, divide &quot;at&quot; to &quot;a/t&quot;.
&quot;r/g / e/ a/t&quot; --&gt; &quot;r/g / e/ a/t&quot; // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is &quot;rgeat&quot; which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.
</pre>

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

<pre>
<strong>Input:</strong> s1 = &quot;abcde&quot;, s2 = &quot;caebd&quot;
<strong>Output:</strong> false
</pre>

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

<pre>
<strong>Input:</strong> s1 = &quot;a&quot;, s2 = &quot;a&quot;
<strong>Output:</strong> true
</pre>

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

<ul>
	<li><code>s1.length == s2.length</code></li>
	<li><code>1 &lt;= s1.length &lt;= 30</code></li>
	<li><code>s1</code> and <code>s2</code> consist of lowercase English letters.</li>
</ul>

class Solution {
    using BT = std::vector<unsigned char>;

    bool solve(const int N,
        const std::vector<std::array<int,26>>& origPSA,
        const std::vector<std::array<int,26>>& scraPSA, 
        BT& dp,
        const int oStart, const int oEnd, const int sStart, const int sEnd,const  int depth) {
            int key = oStart*(N+1)*N + oEnd*N + sStart;
            if (dp[key] != 0) {
                return dp[key] == 2;
            }

            // Let's look at the distribution within the entire thing then
            auto origF = origPSA[oEnd];
            for (int i = 0; i < 26; i++) {
                origF[i] -= origPSA[oStart][i];
            }

            auto scraF = scraPSA[sEnd];
            for (int i = 0; i < 26; i++) {
                scraF[i] -= scraPSA[sStart][i];
            }

            if (origF != scraF) {
                dp[key] = 1;
                return false;
            }


            // If we made it here, then we are all good.
            int len = oEnd - oStart;
            if (len <= 1) {
                dp[key] = 2;
                return true;
            }


            for (int i = 1; i < len; i++) {
                const int oSplit = oStart + i;
                const int sSplit = sStart + i;
                // That is the split point.
                // So we have now 4 options.

                // This is plain, split into x y and run on x and y
                bool partA = solve(N, origPSA, scraPSA, dp, oStart, oSplit, sStart, sSplit, depth+1)
                && solve(N, origPSA, scraPSA, dp, oSplit, oEnd, sSplit, sEnd, depth+1);
                if (partA) {
                    dp[key] = 2;
                    return true;
                }

                const int revSplit = sEnd-i;

                // Now in this case we split it into x y and we want to run y x
                bool partB = solve(N, origPSA, scraPSA, dp, oStart, oSplit, revSplit, sEnd, depth+1)
                && solve(N, origPSA, scraPSA, dp, oSplit, oEnd, sStart, revSplit, depth+1);
                if (partB) {
                    dp[key] = 2;
                    return true;
                }
            }


            dp[key] = 1;
            return false;
        }

public:
    bool isScramble(const std::string& orig, const std::string& scrambled) {
        const int N = orig.size();
        // ok, I understood, so at each point we have to check.
        // So question here, is there any index we can't get this at?

        using IT = std::pair<std::pair<int,int>,std::pair<int,int>>;
        
 
        std::vector<std::array<int,26>> origPSA(N+1);
        origPSA[0] = std::array<int,26>{};
        for (int i = 0; i < N; i++) {
            origPSA[i+1] = origPSA[i];
            origPSA[i+1][orig[i]-'a']++;
        }

        std::vector<std::array<int,26>> scraPSA(N+1);
        scraPSA[0] = std::array<int,26>{};
        for (int i = 0; i < N; i++) {
            scraPSA[i+1] = scraPSA[i];
            scraPSA[i+1][scrambled[i]-'a']++;
        }

        // eventually it will become a guessing game.
        BT seen(N*(N+1)*N, 0);
        return solve(N, origPSA, scraPSA, seen, 0, N, 0, N, 0);

    }
};
10835