1585. Check If String Is Transformable With Substring Sort Operations

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.

 

Solutions

Solution: Greedy

• Time complexity: O(n + 10n -> n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
const isTransformable = function (s, t) {
  const n = s.length;
  const positions = Array.from({ length: 10 }, () => []);

  for (let index = n - 1; index >= 0; index--) {
    const num = Number(s[index]);

    positions[num].push(index);
  }

  for (const char of t) {
    const num = Number(char);

    if (!positions[num].length) return false;
    const index = positions[num].pop();

    for (let smaller = 0; smaller < num; smaller++) {
      if (!positions[smaller].length) continue;
      if (positions[smaller].at(-1) < index) return false;
    }
  }

  return true;
};