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

class Solution {
public:
    int seg_tree[400001];
    string s;
    int built_tree(int node, int l, int r){
        if (l == r) return seg_tree[node] = s[l]-'0';
        int mid = (l+r)/2;
        return seg_tree[node] = min(built_tree(2*node+1, l, mid), built_tree(2*node+2, mid+1, r));
    }

    int query(int node, int ql, int qr, int l, int r){
        if (ql > r || qr < l) return 1e9;
        if (ql<= l && qr >= r) return seg_tree[node];
        int mid = (l+r)/2;
        return min(query(2*node+1, ql, qr,l,  mid), query(2*node+2, ql, qr, mid+1, r));

    }

    int update(int node, int index, int l, int r){

        if (l == r && l == index){
            return seg_tree[node] = 1e9;
        }
        if (index < l || index > r) return 1e9;
        int mid= (l+r)/2;
        return seg_tree[node] = min(update(2*node+1, index,l,mid ), update(2*node+2, index, mid+1,r));
    }
    bool isTransformable(string s, string t) {
       this->s =s;
       built_tree(0, 0, s.size()-1);

       deque<int> digits[10];
       for(int i=0;i<s.size();i++){
           int digit = s[i] - '0';
           digits[digit].push_back(i);
       }
    //    cout << query(0, 2,3,0,s.size()-1) << endl;
       for(int i=0,j=0;i<t.size();i++){
           int digit = t[i]-'0';
           if (digits[digit].empty()) return false;
           int index = digits[digit].front();
           s[index] = '_';
           
           digits[digit].pop_front();
           int mn = query(0,j, index, 0, s.size()-1);
        //    cout << "mn of i " << j << " and index " << index  <<" " <<mn << endl;
           if (mn < digit) return false;
           while(s[j] == '_') j++;
           update(0,index,0,s.size()-1);
       }
       return true;
    

    }
};
22700