<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:
  bool isTransformable(string s, string t) {
    if (getCount(s) != getCount(t))
      return false;

    vector<queue<int>> positions(10);

    for (int i = 0; i < s.length(); ++i)
      positions[s[i] - '0'].push(i);

    // For each digit in `t`, check if we can put this digit in `s` at the same
    // position as `t`. Ensure that all the left digits are equal to or greater
    // than it. This is because the only operation we can perform is sorting in
    // ascending order. If there is a digit to the left that is smaller than it,
    // we can never move it to the same position as in `t`. However, if all the
    // digits to its left are equal to or greater than it, we can move it one
    // position to the left until it reaches the same position as in `t`.
    for (const char c : t) {
      const int d = c - '0';
      const int front = positions[d].front();
      positions[d].pop();
      for (int smaller = 0; smaller < d; ++smaller)
        if (!positions[smaller].empty() && positions[smaller].front() < front)
          return false;
    }
    return true;
  }

 private:
  vector<int> getCount(const string& s) {
    vector<int> count(10);
    for (const char c : s)
      ++count[c - '0'];
    return count;
  }
};
19400