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

#include <bits/stdc++.h>
using namespace std;
#define read(type) readInt<type>() // Fast read
// #define int long long
#define nL "\n"

#define vi vector<int>
#define aint(x) (x).begin(), (x).end()
#define umap unordered_map
#define uset unordered_set
#define MOD 1000000007
#define imax INT_MAX
#define imin INT_MIN
#define exp 1e9
#define sz(x) (int((x).size()))
#define pq_max priority_queue<int>
#define pq_min priority_queue<int, vi, greater<int>>
#define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)

/* FUNCTIONS */
#define f(i, s, e) for (int i = s; i <= e; i++)
#define rf(i, e, s) for (int i = e; i >= s; i--)

class Solution
{
public:
    bool isTransformable(string s, string t)
    {
        int n = s.size();
        vi freq_s(10, 0), freq_t(10, 0);
        for (int i = 0; i < n; i++)
        {
            freq_s[s[i] - '0']++;
            freq_t[t[i] - '0']++;
        }

        for (int i = 0; i < 10; i++)
        {
            if (freq_s[i] != freq_t[i])
            {
                return false;
            }
        }
        vector<deque<int>> pos(10);
        for (int i = 0; i < n; i++)
        {
            pos[s[i] - '0'].push_back(i);
        }
        // stack<int> st;
        // f(i, 0, n - 1)
        // {
        //     st.push(s[i] - '0');
        // }
        // stack<int> temp;

        // cout<<"pos"<<nL;
        // for (int i = 0; i < 10; i++)
        // {
        //     cout << i << " : ";
        //     for (auto x : pos[i])
        //     {
        //         cout << x << " ";
        //     }
        //     cout << nL;
        // }

        rf(i, n - 1, 0)
        {
            int tar_digit = t[i] - '0';
            // if in right we get larger digit than target digit then we can't transform
            // cout<<"tar_digit : "<<tar_digit<<nL;
            f(digit, tar_digit + 1, 9)
            {
                if (pos[digit].empty())
                {
                    continue;
                }
                if (pos[digit].back() > pos[tar_digit].back())
                {
                    return false;
                }
            }

            pos[tar_digit].pop_back();

            // if in right we get smaller digit than target digit then we can transform
        }
        return true;
    }
};
19500