Check If String Is Transformable With Substring Sort Operations

Given two strings s and t, you want to 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 string s into string 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

Example 4:

Input: s = "1", t = "2"
Output: false

Constraints:

s.length == t.length
1 <= s.length <= 105
s and t only contain digits from '0' to '9'.

Solution:

Intuition:

Start from the last digit and move towards the first one, since we can move digits to the right - because we can sort substrings in ascending order
To move digit to the right you can just sort two digits: "5123" -> "1523" -> "1523" -> "1253" -> "1253" -> "1235"
We can move digit A to the right, if digits on the way are less than digit A
- Ex: "5123", we can move "5" to any position to the right, since all digits on the way are less that "5"
- Ex: "57", we can NOT move "5", since there is "7" to the right

class Solution {
    public boolean isTransformable(String s, String t) {
        // positions of all digits
        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'].push(i);
        }
        for (int i = t.length() - 1; i >= 0; i --) {
            int targetDigit = t.charAt(i) - '0';
            if (pos[targetDigit].size() == 0) {
                return false;
            }
            int targetDigitIndexInS = pos[targetDigit].pop();
            // check that there are no bigger digits on the way 
            for (int j = targetDigit + 1; j < 10; j ++) {
                if (pos[j].size() > 0 && pos[j].peekFirst() > targetDigitIndexInS) {
                    return false;
                }
            }
        }
        return true;
    }
}