<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 FenwickTree{
public:
    vector<int> mList;
    FenwickTree(int n){
        mList.resize(n,0);
    }
    void update(int idx,int value){
        while(idx < mList.size()){
            mList[idx] += value;
            idx += (idx & -idx);
        }
    }
    int sum(int idx){
        int ret = 0;
        while(idx > 0){
            ret += mList[idx];
            idx -= (idx & -idx);
        }
        return ret;
    }
};

class Solution {
public:
    bool isTransformable(string s, string t) {
        if(s.length() != t.length()){
            return false;
        }
        int N = s.length();
        vector<deque<int>> idxList(10);

        FenwickTree ft(N+1);

        for(int i = 0;i < N;++i ){
            char c = s[i];
            idxList[c-'0'].push_back(i);
        }
        int i = 0;
        while(i < N){
            char cs = s[i];
            char ct = t[i];
            if(cs == ct){
                idxList[ct-'0'].pop_front();
            }
            else{
                if(cs < ct){
                    return false;
                }
                else{
                    if(idxList[ct-'0'].empty()){
                        return false;
                    }
                    int oldIdx = idxList[ct-'0'].front();
                    int pos = oldIdx + ft.sum(oldIdx+1);
                    idxList[ct-'0'].pop_front();
                    for(int prev = 0;prev < (ct-'0');++prev){
                        if(idxList[prev].size() > 0 &&
                                idxList[prev].front() + ft.sum(1+idxList[prev].front()) < pos){
                            return false;
                        }
                    }

                    ft.update(oldIdx+1,-1);
                    ft.update(1,1);
                    s.erase(s.begin() + pos);
                    s.insert(s.begin() + i,ct);
                }
            }
            i++;
        }
        return true;
    }
};
23300