# Check If String Is Transformable With Substring Sort Operations
**Difficulty:** HARD
[External](https://leetcode.com/problems/check-if-string-is-transformable-with-substring-sort-operations)
Canonical: https://scaleengineer.com/dsa/problems/check-if-string-is-transformable-with-substring-sort-operations
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** String
---
## 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 `"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.

# Approaches
## Naive Greedy Simulation
This approach simulates the process of building the target string `t` from `s` in a greedy manner. We iterate through `t` from left to right. For each character `t[i]`, we find its earliest available occurrence in `s` and check if it can be moved to the current position. A move is possible only if there are no smaller, un-used characters to its left in `s` that would block it.
**Time:** O(N^2), where N is the length of the strings. The outer loop runs N times (for each character in `t`). Inside, we have two nested loops that, in the worst case, scan through `s`. This results in a quadratic time complexity. · **Space:** O(N), where N is the length of the string. This is for the `used` boolean array to track which characters have been consumed.
**Pros:** The logic is straightforward and directly models the constraints of the problem.; It's relatively easy to implement without complex data structures.
**Cons:** The time complexity is quadratic, which can be too slow for large inputs (like N=10^5).
### Explanation
The fundamental observation is that the sorting operation allows smaller characters to move to the left past larger characters, but a character can never move to the left of a character that is smaller than it. This establishes a relative ordering constraint.

This approach greedily constructs `t` one character at a time. For `t[0]`, we need to find a character in `s` that can become the first character. Then for `t[1]`, we find a character from the remaining ones in `s` that can become the second, and so on. The greedy choice is to always use the leftmost available character from `s` that matches the required character `t[i]`.

To implement this, we first verify that `s` and `t` are anagrams. Then, we iterate through `t`. For each `t[i]`, we scan `s` to find the first unused character `s[j]` that equals `t[i]`. To check if this `s[j]` can be moved into position, we must ensure no smaller unused character `s[k]` exists at an index `k < j`. If such a blocking character exists, the transformation is impossible. Otherwise, we mark `s[j]` as used and continue to the next character of `t`.

```java
import java.util.Arrays;

class Solution {
    public boolean isTransformable(String s, String t) {
        // Anagram check
        int[] counts = new int[10];
        for (char c : s.toCharArray()) {
            counts[c - '0']++;
        }
        for (char c : t.toCharArray()) {
            counts[c - '0']--;
        }
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }

        int n = s.length();
        boolean[] used = new boolean[n];

        for (int i = 0; i < n; i++) {
            char targetChar = t.charAt(i);
            int found_j = -1;

            // Find the leftmost unused character in s that matches targetChar
            for (int j = 0; j < n; j++) {
                if (!used[j] && s.charAt(j) == targetChar) {
                    found_j = j;
                    break;
                }
            }

            // Check for smaller characters to the left of found_j
            for (int k = 0; k < found_j; k++) {
                if (!used[k] && s.charAt(k) < targetChar) {
                    return false; // Blocked by a smaller character
                }
            }
            
            used[found_j] = true;
        }

        return true;
    }
}
```
### Algorithm
*   First, check if `s` and `t` are anagrams. If their character counts don't match, it's impossible to transform `s` to `t`, so return `false`.
*   Initialize a boolean array `used` of size `n` (the length of the strings) to all `false`. This array will keep track of which characters from `s` have been used.
*   Iterate through the target string `t` from left to right, with index `i` from `0` to `n-1`.
*   For each character `t[i]`, find the first available matching character in `s`. This means finding the smallest index `j` such that `s[j] == t[i]` and `used[j]` is `false`.
*   Once this character `s[j]` is found, check if it's possible to move it to the current position. A character can be moved left past any larger or equal characters. It is only blocked by smaller characters. Therefore, we must check if there are any unused characters to the left of `s[j]` that are smaller than it. Iterate from `k = 0` to `j-1`. If we find an index `k` where `used[k]` is `false` and `s[k] < s[j]`, it means `s[j]` is blocked. The transformation is impossible, so return `false`.
*   If `s[j]` is not blocked, it means we can use it to form `t[i]`. Mark it as used by setting `used[j] = true`.
*   If the loop completes for all characters in `t`, it means a valid transformation sequence exists. Return `true`.

## Optimized Greedy with Position Pointers
This approach refines the greedy strategy by optimizing the search for characters and their blockers. Instead of repeatedly scanning the string `s`, we pre-process it to store the indices of each character. This allows us to find the position of the next available character and check for blocking characters in constant time (per digit), leading to a much faster overall algorithm.
**Time:** O(N). The anagram check takes O(N). Populating the `positions` data structure takes O(N). The main loop iterates N times. Inside this loop, we have another loop that runs at most 10 times (for digits 0-9). Thus, the work inside the main loop is O(10 * N) = O(N). The total time complexity is linear. · **Space:** O(N), where N is the length of the strings. The `positions` data structure stores a total of N indices. The character count array takes constant space O(1) as there are only 10 digits.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; It is an optimal solution for this problem.
**Cons:** Requires more complex data structures (array of lists/queues) compared to the naive approach.; Uses more space to store all indices from the original string.
### Explanation
The core logic remains the same as the naive approach: a character `c` at index `j` in `s` can be moved to the current leftmost position if and only if there are no smaller available characters at indices less than `j`. The key to optimization is to avoid the `O(N)` scans in each step.

We can achieve this by pre-computing the locations of all digits. We use an array of queues, say `positions`, where `positions[d]` stores all indices of digit `d` in `s` in increasing order.

We then iterate through `t`. For each `t[i]`, we identify the character `c = t[i]`. The greedy choice is to use the first available `c` from `s`, whose index `j` is at the front of `positions[c - '0']`. To check if this is a valid move, we must ensure that for any digit `d < c - '0'`, the first available `d` is not to the left of `j`. We can quickly check this by peeking at the front of `positions[d]` for all `d < c - '0'`. If we find any such blocking character, we return `false`. Otherwise, the move is valid, and we remove `j` from its queue (`positions[c - '0'].poll()`) to mark it as used.

This pre-computation allows all lookups and checks inside the main loop to be very fast, reducing the complexity from quadratic to linear.

```java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public boolean isTransformable(String s, String t) {
        // Anagram check
        int[] counts = new int[10];
        for (char c : s.toCharArray()) {
            counts[c - '0']++;
        }
        for (char c : t.toCharArray()) {
            counts[c - '0']--;
        }
        for (int count : counts) {
            if (count != 0) {
                return false;
            }
        }

        // Pre-process s to store indices of each digit
        List<Queue<Integer>> positions = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            positions.add(new LinkedList<>());
        }
        for (int i = 0; i < s.length(); i++) {
            positions.get(s.charAt(i) - '0').add(i);
        }

        // Greedily build t
        for (int i = 0; i < t.length(); i++) {
            int digit = t.charAt(i) - '0';
            int pos = positions.get(digit).peek();

            // Check for smaller blocking digits
            for (int smallerDigit = 0; smallerDigit < digit; smallerDigit++) {
                if (!positions.get(smallerDigit).isEmpty() && positions.get(smallerDigit).peek() < pos) {
                    return false;
                }
            }
            
            // Consume the digit
            positions.get(digit).poll();
        }

        return true;
    }
}
```
### Algorithm
*   First, perform an anagram check. If `s` and `t` don't have the same character counts, return `false`.
*   Pre-process `s` to store the indices of each digit. An array of queues or lists, `positions`, is suitable, where `positions[d]` holds a sorted list of indices where digit `d` appears in `s`.
*   Iterate through `t` from `i = 0` to `n-1`. Let `c` be the character `t[i]`.
*   The greedy strategy dictates we must use the leftmost available occurrence of `c` from `s`. We can get its index, `j`, by looking at the front of the queue `positions[c - '0']`.
*   Now, check if this move is valid. For every digit `d` that is smaller than `c` (i.e., `d < c - '0'`), check if its leftmost available occurrence is at an index smaller than `j`. If `!positions[d].isEmpty()` and `positions[d].peek() < j`, it means `c` is blocked by a smaller digit `d`. Return `false`.
*   If `c` is not blocked by any smaller digit, the move is valid. We consume this occurrence of `c` by removing its index from the front of its queue (e.g., `positions[c - '0'].poll()`).
*   If the loop completes successfully for all characters of `t`, return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean isTransformable(String s, String t) {
    Deque<Integer>[] pos = new Deque[10];
    Arrays.setAll(pos, k->new ArrayDeque<>());
    for (int i = 0; i < s.length(); ++i) {
      pos[s.charAt(i) - '0'].offer(i);
    }
    for (int i = 0; i < t.length(); ++i) {
      int x = t.charAt(i) - '0';
      if (pos[x].isEmpty()) {
        return false;
      }
      for (int j = 0; j < x; ++j) {
        if (!pos[j].isEmpty() && pos[j].peek() < pos[x].peek()) {
          return false;
        }
      }
      pos[x].poll();
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isTransformable(string s, string t) {
    queue<int> pos[10];
    for (int i = 0; i < s.size(); ++i) {
      pos[s[i] - '0'].push(i);
    }
    for (char &c : t) {
      int x = c - '0';
      if (pos[x].empty()) {
        return false;
      }
      for (int j = 0; j < x; ++j) {
        if (!pos[j].empty() && pos[j].front() < pos[x].front()) {
          return false;
        }
      }
      pos[x].pop();
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def isTransformable(self, s: str, t: str) -> bool: pos = defaultdict(deque) for i, c in enumerate(s): pos[int(c)]. append(i) for c in t: x = int(c) if not pos[x] or any(pos[i] and pos[i][0] < pos[x][0] for i in range(x)): return False pos[x]. popleft() return True

```