Check If String Is Transformable With Substring Sort Operations

LeetCode Check If String Is Transformable With Substring Sort Operations (problem 1585) asks a deceptively simple question. You have two strings s and t, both the same length, both consisting only of digits 0 through 9. You can pick any non-empty substring of s and sort it in non-decreasing order, and you can do this as many times as you want. Can you turn s into t?

Why this problem matters

On the surface it looks like a simulation problem, but simulating every possible sequence of substring sorts would be impossibly slow. The real challenge is recognizing what sorting operations can and cannot do. Once you understand the structural constraint, the solution is a clean greedy pass with digit queues.

This problem tests your ability to reason about invariants of sorting operations, a skill that transfers to many string and array transformation problems.

The key insight

Sorting a substring is equivalent to performing adjacent swaps within that substring. It is the same operation as running bubble sort on that range. A smaller digit can move leftward past any number of larger digits (you just sort the substring containing all of them). But a larger digit can never move leftward past a smaller one, because sorting only produces non-decreasing order.

This gives you a clean rule: for each character in t, processed from left to right, find the next available occurrence of that digit in s. If there is any smaller digit that appears before it in s and has not yet been consumed, the transformation is impossible. That smaller digit would block the target digit from bubbling left to the correct position.

The solution

from collections import deque

def is_transformable(s: str, t: str) -> bool:
    pos = [deque() for _ in range(10)]
    for i, ch in enumerate(s):
        pos[int(ch)].append(i)

    for ch in t:
        d = int(ch)
        if not pos[d]:
            return False
        idx = pos[d][0]
        for smaller in range(d):
            if pos[smaller] and pos[smaller][0] < idx:
                return False
        pos[d].popleft()

    return True

The algorithm builds ten queues, one for each digit 0 through 9. Each queue stores the indices where that digit appears in s, in order from left to right.

Then you process t one character at a time. For each digit d you need to place, you look at the front of queue d to find where the next available d sits in s. Before you can use it, you check every digit smaller than d. If any smaller digit has an unused occurrence that appears earlier in s (an index smaller than idx), that smaller digit is blocking your target. It cannot be jumped over, so you return False.

If no smaller digit blocks, you consume the d by popping it from its queue and move on to the next character in t.

Visual walkthrough

At each step, the algorithm only needs to check the front of each smaller digit's queue. Because the queues store indices in order, the front always represents the earliest unplaced occurrence. If that earliest occurrence is before our target digit, it blocks. Otherwise, the path is clear.

Complexity analysis

Time is O(10 * n) where n is the length of the string. For each of the n characters in t, you check at most 10 digit queues to see if a smaller digit blocks. Since 10 is a constant, this simplifies to O(n).

Space is O(n) for the ten queues, which together hold n indices total (one per character in s).

The building blocks

1. Index queues for digit tracking

The pattern of storing indices of each digit in a queue:

pos = [deque() for _ in range(10)]
for i, ch in enumerate(s):
    pos[int(ch)].append(i)

This gives you O(1) access to the next available occurrence of any digit. You will see this "bucket by value, store indices" technique in problems involving digit frequency, character scheduling, and any scenario where you need to process specific values in order of their positions.

2. Blocking check for smaller digits

The core validation loop:

idx = pos[d][0]
for smaller in range(d):
    if pos[smaller] and pos[smaller][0] < idx:
        return False

This checks whether any smaller digit sits to the left of our target in the remaining (unconsumed) portion of s. If it does, that digit would need to be placed first, but t wants our target digit next. The conflict is irreconcilable, so the answer is False. This pattern of checking for "blocking elements" by comparing front-of-queue indices is specific to problems involving constrained reordering.

Edge cases

• Identical strings. When s equals t, every digit is found immediately with no blockers. Returns True.
• Single character. If both strings have length 1, they must be equal. The algorithm handles this: either the digit matches or the queue is empty.
• All same digit. If every character is the same digit (e.g., "3333"), any permutation is the identity. Returns True if s equals t, False otherwise (but since all characters are the same, they must be equal).
• Reverse sorted. s = "54321", t = "12345". Every smaller digit needs to move left past all larger ones, and no smaller digit blocks any other smaller digit. Returns True.
• Impossible due to blocking. s = "12", t = "21". To place 2 first, you need the 2 at index 1, but the 1 at index 0 is smaller and blocks it. Returns False.
• Different character frequencies. If s and t do not have the same digit counts, the queue for some digit will run empty when you need it. Returns False.

From understanding to recall

The code for this problem is short, but the reasoning behind it is subtle. You need to internalize why sorting a substring is equivalent to bubble sort, why smaller digits block leftward movement of larger ones, and why checking the front of each smaller queue is sufficient.

When you review this problem, walk through the blocking check by hand. Pick a digit in t, find it in s, and ask: is there a smaller digit to its left that has not been consumed yet? That mental exercise is the core of the algorithm. Once you can run it in your head without hesitation, the code writes itself.

Related posts

• Orderly Queue - String transformation with limited operations and the bubble sort invariant
• Next Permutation - Understanding digit ordering constraints in permutation problems
• Largest Number - Custom sorting of digit strings where comparison order matters

CodeBricks breaks this problem into its digit-queue setup and blocking-check building blocks, then drills each one independently with spaced repetition. You practice the queue initialization, the greedy scan, and the blocker check from memory until the pattern is automatic. When a string transformation problem appears in your interview, you recognize the invariant and write the solution without hesitation.