Problem statement

https://leetcode.com/problems/check-if-string-is-transformable-with-substring-sort-operations/

Solution

Quite difficult problem for me, because we need to use greedy approach here. There are couple of observations we need to deal with:

  1. Instead of sorting substring, we can replace it by operation: given two adjacent elements x > y, swap them.
  2. Imagine, we have d......... for the first string and x........ for the second. Then we need to find the first d in the second string: x[A]d[B], where [A] and [B] are some strings. Why we need to find the first occurrence? Because we can not swap elements with x = y. So, if we did not found the place to swap with, we return False. Also we need to make sure, that all elements in x[A] are smaller than d: again when we drag element d to the right, we need this condition.
  3. What we keep is places: deque of places for each digit: in this way we can quickly check two conditions above.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def isTransformable(self, s, t):
        s, t = [*map(int, s)], [*map(int, t)]
        places = [deque() for _ in range(10)]
        for i, dig in enumerate(s):
            places[dig].append(i)
        
        for dig in t:
            if not places[dig]:
                return False 
            i = places[dig][0]
            for j in range(dig):
                if places[j] and places[j][0] < i:
                    return False
            places[dig].popleft()
        return True