Given two strings s and t of equal length consisting of digits from '0' to '9', determine if it is possible to transform s into t using any number of the following operation:
s and sort it in non-decreasing order.
You can perform the operation as many times as you want, on any substring, including overlapping ones. Your goal is to check if you can make s equal to t by applying these operations.
Constraints:
1 <= s.length == t.length <= 10^5s and t consist of digits only.
At first glance, it may seem that since we can sort any substring, we can always transform s into t if they are anagrams. However, the operation only allows sorting substrings, never moving a digit past a smaller digit that is to its right.
For example, you cannot move a '2' past a '1' that is after it, because sorting will always keep the '1' before '2' in any substring containing both. This means that, for each digit in t, we must check if we can move that digit from its current position in s to the required position in t without jumping over a smaller digit.
Brute-force would try all possible sorts, but this is infeasible for large strings. We need an optimized way to track whether, for each digit in t, we can legally move it to its target position without violating the sorting constraints.
We approach this problem by simulating the process of transforming s into t digit by digit, ensuring that at each step, the movement of digits does not violate the sorting rule.
s. This allows us to efficiently access the next available position of each digit.
t from left to right. For each character ch in t, do the following:
ch in s (from the corresponding queue).ch to its position in t, check if there is any smaller digit (i.e., digit less than ch) that appears before this occurrence in s and hasn't been used yet. If so, transformation is impossible, because sorting a substring cannot move ch past a smaller digit to its right.ch and continue.t this way, return True. Otherwise, return False.
We use queues (or deques) for each digit so that we can efficiently pop the next available index for each digit. To check for blocking digits, we only need to check the front of the queues for digits smaller than ch.
Let's take s = "84532" and t = "34852".
s:
t:
s is at index 3.n.
O(n * 10) = O(n), where n is the length of s and t. For each position, we may check up to 10 digit queues.
O(n) for storing the positions of each digit in queues.
The key insight is that sorting a substring cannot move a digit past a smaller digit to its right. By using queues to track the positions of each digit in s, we efficiently simulate the transformation process and check for any blocking digits. This approach is both efficient and elegant, leveraging the properties of queue data structures and digit ordering.
from collections import deque
class Solution:
def isTransformable(self, s: str, t: str) -> bool:
pos = [deque() for _ in range(10)]
for i, ch in enumerate(s):
pos[int(ch)].append(i)
for ch in t:
d = int(ch)
if not pos[d]:
return False
idx = pos[d][0]
# Check for any smaller digit that blocks this one
for smaller in range(d):
if pos[smaller] and pos[smaller][0] < idx:
return False
pos[d].popleft()
return True
#include <vector>
#include <deque>
#include <string>
using namespace std;
class Solution {
public:
bool isTransformable(string s, string t) {
vector<deque<int>> pos(10);
for (int i = 0; i < s.size(); ++i) {
pos[s[i] - '0'].push_back(i);
}
for (char ch : t) {
int d = ch - '0';
if (pos[d].empty()) return false;
int idx = pos[d].front();
for (int smaller = 0; smaller < d; ++smaller) {
if (!pos[smaller].empty() && pos[smaller].front() < idx)
return false;
}
pos[d].pop_front();
}
return true;
}
};
import java.util.*;
class Solution {
public boolean isTransformable(String s, String t) {
Deque<Integer>[] pos = new Deque[10];
for (int i = 0; i < 10; ++i) pos[i] = new ArrayDeque<>();
for (int i = 0; i < s.length(); ++i) {
pos[s.charAt(i) - '0'].add(i);
}
for (char ch : t.toCharArray()) {
int d = ch - '0';
if (pos[d].isEmpty()) return false;
int idx = pos[d].peek();
for (int smaller = 0; smaller < d; ++smaller) {
if (!pos[smaller].isEmpty() && pos[smaller].peek() < idx)
return false;
}
pos[d].poll();
}
return true;
}
}
var isTransformable = function(s, t) {
const pos = Array.from({length: 10}, () => []);
for (let i = 0; i < s.length; ++i) {
pos[parseInt(s[i])].push(i);
}
let ptr = Array(10).fill(0);
for (let i = 0; i < t.length; ++i) {
let d = parseInt(t[i]);
if (ptr[d] >= pos[d].length) return false;
let idx = pos[d][ptr[d]];
for (let smaller = 0; smaller < d; ++smaller) {
if (ptr[smaller] < pos[smaller].length && pos[smaller][ptr[smaller]] < idx)
return false;
}
ptr[d]++;
}
return true;
};