<p>Given two strings <code>s</code> and <code>t</code>, transform string <code>s</code> into string <code>t</code> using the following operation any number of times:</p>

<ul>
	<li>Choose a <strong>non-empty</strong> substring in <code>s</code> and sort it in place so the characters are in <strong>ascending order</strong>.

	<ul>
		<li>For example, applying the operation on the underlined substring in <code>&quot;1<u>4234</u>&quot;</code> results in <code>&quot;1<u>2344</u>&quot;</code>.</li>
	</ul>
	</li>
</ul>

<p>Return <code>true</code> if <em>it is possible to transform <code>s</code> into <code>t</code></em>. Otherwise, return <code>false</code>.</p>

<p>A <strong>substring</strong> is a contiguous sequence of characters within a string.</p>

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

<pre>
<strong>Input:</strong> s = &quot;84532&quot;, t = &quot;34852&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> You can transform s into t using the following sort operations:
&quot;84<u>53</u>2&quot; (from index 2 to 3) -&gt; &quot;84<u>35</u>2&quot;
&quot;<u>843</u>52&quot; (from index 0 to 2) -&gt; &quot;<u>348</u>52&quot;
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;34521&quot;, t = &quot;23415&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> You can transform s into t using the following sort operations:
&quot;<u>3452</u>1&quot; -&gt; &quot;<u>2345</u>1&quot;
&quot;234<u>51</u>&quot; -&gt; &quot;234<u>15</u>&quot;
</pre>

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

<pre>
<strong>Input:</strong> s = &quot;12345&quot;, t = &quot;12435&quot;
<strong>Output:</strong> false
</pre>

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

<ul>
	<li><code>s.length == t.length</code></li>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> and <code>t</code> consist of only digits.</li>
</ul>

/*
find t[s]

move through target (i = 0 to n-1).
if s[i] == t[i] then remove hm[d = t[i]-'0'].erase(i) continue
else find hm[d] first value - dfirst
    loop j from 0 to d-1
    find hm[j].lower_bound(dfirst)...if > hm[j].begin() then there exists a lower value to the left so return false

    after loop hm[d].erase(dfirst)

return true
*/

class Solution {
public:
    bool isTransformable(string s, string t) {
        map<int,set<int>> hm;
        int n = s.length();

        string s2 = s, t2 = t;
        sort(s2.begin(), s2.end());
        sort(t2.begin(), t2.end());
        if (s2 != t2) return false;


        for (int i = 0; i < n; i++) hm[s[i]-'0'].insert(i);

        for (int i = 0; i < n; i++) {
            int d = t[i] - '0';

            /*
            if (s[i] == t[i]) {
                hm[d].erase(i); continue;
            }
            */
            if (!hm.count(d)) return false;
            auto it = hm[d].begin();
            int dfirst = (*it);
            //cout << "\ni = " << i << "; d = " << d << "; dfirst = " << dfirst;

            for (int j = 0; j < d; j++) {
                if (hm.count(j)) {
                    auto it = hm[j].begin();
                    int jfirst = (*it);
                    //cout << "\tj = " << j << "; jfirst = " << jfirst;
                    if (jfirst < dfirst) return false;
                }
            }
            hm[d].erase(dfirst);
            if (!hm[d].size()) hm.erase(d);
        }
        return true;
    }
};
65800