Check If String Is Transformable With Substring Sort Operations - Solution & Explanation

Problem Overview: You are given two strings s and t consisting of digits. You can repeatedly choose any substring of s and sort it in ascending order. The task is to determine whether these operations can transform s into t.

Approach 1: Greedy Algorithm with Position Tracking (O(n) time, O(n) space)

This approach processes t from left to right and greedily matches each digit with the earliest valid occurrence in s. Maintain queues (or lists) storing indices of each digit 0–9 in s. When you need digit d for the next position in t, pop the earliest index from the queue for d. The key constraint: no smaller digit can appear before this index in s that hasn’t been used yet. A smaller digit would block the transformation because sorting operations cannot move a larger digit ahead of a smaller one that appears earlier. Checking digits 0..d-1 ensures the move is valid. This greedy ordering directly models the restrictions imposed by substring sorting. It works in linear time because each index is processed once.

Approach 2: Index Matching with Character Buckets (O(n) time, O(n) space)

This method groups positions of digits in s into buckets indexed by digit value. While scanning t, you match each character with the next available index from its corresponding bucket. Before accepting that index, verify that no smaller digit bucket has an earlier unused index. If such a digit exists, the transformation would require moving a larger digit ahead of a smaller one, which substring sorting cannot achieve. Conceptually this approach is similar to the greedy solution but emphasizes bucket-based indexing and pointer tracking. The logic focuses on validating ordering constraints across digit groups rather than directly simulating operations.

Both approaches rely on understanding how sorting a substring affects relative order. Sorting can move smaller digits left but cannot move larger digits ahead of smaller ones already positioned earlier. This constraint turns the problem into verifying whether the relative ordering of digits in s can satisfy the target sequence in t. Efficient tracking of indices with queues or buckets avoids repeated scans.

Recommended for interviews: The greedy position-tracking solution is what most interviewers expect. It demonstrates a strong understanding of ordering constraints and uses efficient data structures from string processing and greedy strategy. A brute-force simulation of substring sorting would be far too slow, but discussing why it fails helps show problem intuition before presenting the optimal linear solution.