<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>

struct Segtree {
    vector<int> tree;
    Segtree(int n) : tree(4 * n + 5) {}
    void build(int v, int s, int e, vector<int>& ar) {
        if (s == e) { tree[v] = ar[s]; return; }
        int mid = (s + e) >> 1;
        build(v << 1, s, mid, ar);
        build(v << 1 | 1, mid + 1, e, ar);
        tree[v] = min(tree[v << 1], tree[v << 1 | 1]);
    }
    void upd(int v, int s, int e, int pos, int val) {
        if (s == e) { tree[v] = val; return; }
        int mid = (s + e) >> 1;
        if (pos <= mid) upd(v << 1, s, mid, pos, val);
        else upd(v << 1 | 1, mid + 1, e, pos, val);
        tree[v] = min(tree[v << 1], tree[v << 1 | 1]);
    }
    int get(int v, int s, int e, int l, int r) {
        if (s == l && e == r) return tree[v];
        int mid = (s + e) >> 1;
        if (r <= mid) return get(v << 1, s, mid, l, r);
        else if (l >= mid + 1) return get(v << 1, mid + 1, e, l, r);
        return min(get(v << 1, s, mid, l, mid), get(v << 1 | 1, mid + 1, e, mid + 1, r));
    }
};

class Solution {
public:
    bool isTransformable(string s, string t) {
        int n = s.length();
        vector<int> ptr(10);
        vector<vector<int>> pos(10);
        const int INF = 20;
        vector<int> num(n);
        for (int i = 0; i < n; i++) {
            pos[s[i] - '0'].push_back(i);
            num[i] = s[i] - '0';
        }
        Segtree sgt(n);
        sgt.build(1, 0, n - 1, num);
        for (int i = 0; i < n; i++) {
            int cur = t[i] - '0';
            if (ptr[cur] >= pos[cur].size()) {
                return false;
            }
            int mn = sgt.get(1, 0, n - 1, 0, pos[cur][ptr[cur]]);
            if (mn < cur) return false;
            sgt.upd(1, 0, n - 1, pos[cur][ptr[cur]], INF);
            ptr[cur]++;
        }
        return true;
    }
};
40400