Check If String Is Transformable With Substring Sort Operations — LeetCode 1585 Python Solution

The 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".

Example

Input

s = "84532", t = "34852"

Output

true

Explanation

You can transform s into t using the following sort operations:

Python solution

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

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1585. Check If String Is Transformable With Substring Sort Operations is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems