Problem

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 "1 _4234_ " results in "1 _2344_ ".

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

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

Examples

Example 1

1
2
3
4
5

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

Example 2

1
2
3
4
5

Input: s = "34521", t = "23415"
Output: true
Explanation: You can transform s into t using the following sort operations:
"_3452_ 1" -> "_2345_ 1"
"234 _51_ " -> "234 _15_ "

Example 3

1
2

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

Constraints

  • s.length == t.length
  • 1 <= s.length <= 10^5
  • s and t consist of only digits.

Solution

Method 1 – Greedy Index Tracking with Queues

Intuition

We want to transform s into t by repeatedly sorting substrings. The only way to move a digit left is to sort a substring that includes it and all smaller digits to its left. So, for each digit in t, we must ensure that all smaller digits in s do not block it from moving to its position.

Reasoning

For each digit in t, we find its next occurrence in s (using queues for each digit). If any smaller digit appears before it in s, it cannot be moved left past that digit, so the transformation is impossible. This greedy approach works because sorting can only move a digit left if all smaller digits are already to its right.

Approach

  1. For each digit 0-9, create a queue to store the indices of its occurrences in s.
  2. For each character c in t:
    • Pop the leftmost index of c from its queue.
    • For all digits smaller than c, check if their queue is non-empty and their leftmost index is less than the current index. If so, return false.
  3. If all characters in t are matched, return true.

Edge cases:

  • If s and t have different digit counts, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    bool isTransformable(string s, string t) {
        vector<queue<int>> pos(10);
        for (int i = 0; i < s.size(); ++i) pos[s[i] - '0'].push(i);
        for (char c : t) {
            int d = c - '0';
            if (pos[d].empty()) return false;
            int idx = pos[d].front(); pos[d].pop();
            for (int k = 0; k < d; ++k) {
                if (!pos[k].empty() && pos[k].front() < idx) return false;
            }
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func isTransformable(s string, t string) bool {
    pos := make([][]int, 10)
    for i := range s {
        d := s[i] - '0'
        pos[d] = append(pos[d], i)
    }
    idx := make([]int, 10)
    for i := 0; i < len(t); i++ {
        d := t[i] - '0'
        if idx[d] >= len(pos[d]) {
            return false
        }
        p := pos[d][idx[d]]
        for k := 0; k < int(d); k++ {
            if idx[k] < len(pos[k]) && pos[k][idx[k]] < p {
                return false
            }
        }
        idx[d]++
    }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public boolean isTransformable(String s, String t) {
        Queue<Integer>[] pos = new Queue[10];
        for (int i = 0; i < 10; i++) pos[i] = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) pos[s.charAt(i) - '0'].add(i);
        for (char c : t.toCharArray()) {
            int d = c - '0';
            if (pos[d].isEmpty()) return false;
            int idx = pos[d].poll();
            for (int k = 0; k < d; k++) {
                if (!pos[k].isEmpty() && pos[k].peek() < idx) return false;
            }
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun isTransformable(s: String, t: String): Boolean {
        val pos = Array(10) { ArrayDeque<Int>() }
        for (i in s.indices) pos[s[i] - '0'].add(i)
        for (c in t) {
            val d = c - '0'
            if (pos[d].isEmpty()) return false
            val idx = pos[d].removeFirst()
            for (k in 0 until d) {
                if (pos[k].isNotEmpty() && pos[k].first() < idx) return false
            }
        }
        return true
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def is_transformable(self, s: str, t: str) -> bool:
        from collections import deque
        pos = [deque() for _ in range(10)]
        for i, c in enumerate(s):
            pos[int(c)].append(i)
        for c in t:
            d = int(c)
            if not pos[d]:
                return False
            idx = pos[d].popleft()
            for k in range(d):
                if pos[k] and pos[k][0] < idx:
                    return False
        return True
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn is_transformable(s: String, t: String) -> bool {
        use std::collections::VecDeque;
        let mut pos = vec![VecDeque::new(); 10];
        for (i, c) in s.chars().enumerate() {
            pos[c as usize - '0' as usize].push_back(i);
        }
        for c in t.chars() {
            let d = c as usize - '0' as usize;
            if pos[d].is_empty() {
                return false;
            }
            let idx = pos[d].pop_front().unwrap();
            for k in 0..d {
                if !pos[k].is_empty() && *pos[k].front().unwrap() < idx {
                    return false;
                }
            }
        }
        true
    }
}

Complexity

  • ⏰ Time complexity: O(n), as each character is processed a constant number of times and all queue operations are amortized constant time.
  • 🧺 Space complexity: O(n), as we store the indices of each digit in queues.