Check If String Is Transformable With Substring Sort Operations in Python

Problem Description

So, you think you can just rearrange a string like you rearrange your sock drawer? Well, think again! The problem at hand is to determine if you can transform string s into string t using a series of substring sort operations. Imagine you have a jumbled mess of socks (or digits, in this case) and you can only sort them in ascending order. The catch? You can only sort substrings!

In simpler terms, if you have s = "34521" and t = "12345", you need to figure out if you can sort s into t by only sorting parts of it. Spoiler alert: it’s not as easy as it sounds!

Code Solution

class Solution:
    def isTransformable(self, s: str, t: str) -> bool:
        if collections.Counter(s) != collections.Counter(t):
            return False

        positions = [collections.deque() for _ in range(10)]

        for i, c in enumerate(s):
            positions[int(c)].append(i)

        for c in t:
            d = int(c)
            front = positions[d].popleft()
            for smaller in range(d):
                if positions[smaller] and positions[smaller][0] < front:
                    return False

        return True
    

Approach

The approach here is as clever as a cat trying to catch a laser pointer. First, we check if both strings have the same characters using collections.Counter. If they don’t, we can’t transform s into t, so we return False.

Next, we create a list of deques to keep track of the positions of each digit in s. For each digit in t, we check if we can place it in the correct position in s while ensuring that all smaller digits to the left are in their rightful places. If we find a smaller digit that’s in the way, we return False. If we can place all digits correctly, we return True.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s. We traverse the string a couple of times, but it’s still linear.

Space Complexity: O(1), since we are using a fixed-size list of deques (10 for digits 0-9).

Real-World Example

Imagine you’re at a party, and you have a group of friends (digits) who want to line up for a photo. However, they can only move to the left if everyone to their left is either the same height or taller. If someone shorter is in front of them, they can’t get into position. This is exactly what our algorithm is doing—ensuring that each digit can find its place without being blocked by smaller digits.