Check If String Is Transformable With Substring Sort Operations

Problem Description

Given two strings s and t, transform string s into string t using the following operation any number of times:

• Choose a non-empty substring in s and sort it in place so the characters are in ascending order.
  • For example, applying the operation on the underlined substring in "14234" results in "12344".

Return true if it is possible to transform s into t. Otherwise, return false.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "84532", t = "34852"
Output: true
Explanation: You can transform s into t using the following sort operations:
"84532" (from index 2 to 3) -> "84352"
"84352" (from index 0 to 2) -> "34852"

Example 2:

Input: s = "34521", t = "23415"
Output: true
Explanation: You can transform s into t using the following sort operations:
"34521" -> "23451"
"23451" -> "23415"

Example 3:

Input: s = "12345", t = "12435"
Output: false

Constraints:

• s.length == t.length
• 1 <= s.length <= 105
• s and t consist of only digits.

Solution (JavaScript)

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isTransformable = function(s, t) {
    // 0-9 的位置
    const pos = new Map([...Array(10)].map((_, i) => [i, []]));
    // 从后往前遍历 s，记录每个数字的位置
    for (let i = s.length - 1; i >= 0; i--) {
        pos.get(+s[i]).push(i);
    }
    for (let i = 0; i < t.length; i++) {
        const key = +t[i];
        const idx = pos.get(key).pop();

        // 如果 t 中的数字在 s 中不存在，或者在 s 中的位置比之前的数字还靠前，则无法转换
        if (idx === undefined) return false;

        // 检查 t 中当前数字之前的数字在 s 中的位置是否都比当前数字靠前
        for (let j = 0; j < key; j++) {
            if (pos.get(j).at(-1) < idx) return false;
        }
    }
    return true;
};