{x}
blog image

Check If String Is Transformable With Substring Sort Operations

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

Return true if it is possible to transform s into t. Otherwise, return false.

A substring is a contiguous sequence of characters within a string.

 

Example 1:

Input: s = "84532", t = "34852"
Output: true
Explanation: You can transform s into t using the following sort operations:
"84532" (from index 2 to 3) -> "84352"
"84352" (from index 0 to 2) -> "34852"

Example 2:

Input: s = "34521", t = "23415"
Output: true
Explanation: You can transform s into t using the following sort operations:
"34521" -> "23451"
"23451" -> "23415"

Example 3:

Input: s = "12345", t = "12435"
Output: false

 

Constraints:

  • s.length == t.length
  • 1 <= s.length <= 105
  • s and t consist of only digits.

Solution Explanation: Checking String Transformability

This problem asks whether string s can be transformed into string t using substring sort operations. The key insight is that we don't need to actually perform the sorts; we only need to check if the relative order of digits can be achieved.

Core Idea: The solution leverages a greedy approach. We track the indices of each digit in s using queues (deque in Python, ArrayDeque in Java, queue in C++). We iterate through t, and for each digit:

  1. Existence Check: Verify that the digit exists in s (its queue is not empty).
  2. Order Check: Ensure that no digit smaller than the current digit in t appears before the current digit's earliest occurrence in s. This is the crucial greedy step. If a smaller digit is ahead, no amount of sorting substrings can fix the order.
  3. Index Update: If the order is valid, remove the earliest occurrence of the digit from its queue.

Time Complexity: O(N*K), where N is the length of the strings and K is the number of unique digits (10 in this case). The nested loop structure dominates the runtime. In the worst case, we might check all digits for each character in t.

Space Complexity: O(N) for the queues (to store indices). This is because we store at most N indices.

Code Explanation (Python):

from collections import defaultdict, deque
 
class Solution:
    def isTransformable(self, s: str, t: str) -> bool:
        pos = defaultdict(deque) # Queues to store indices of each digit
        for i, c in enumerate(s):
            pos[int(c)].append(i)  #Store the index of each digit in s.
 
        for c in t:
            x = int(c)
            if not pos[x]: #If the digit is not found
                return False
            for j in range(x): #Check if smaller digits appear before
                if pos[j] and pos[j][0] < pos[x][0]:
                    return False
            pos[x].popleft() #Remove the earliest occurrence.
 
        return True

Code Explanation (Java):

import java.util.*;
 
class Solution {
    public boolean isTransformable(String s, String t) {
        Deque<Integer>[] pos = new Deque[10]; //Array of Deques to store indices
        Arrays.setAll(pos, k -> new ArrayDeque<>()); //Initialize the array
 
        for (int i = 0; i < s.length(); ++i) {
            pos[s.charAt(i) - '0'].offer(i); //Store the index of each digit in s.
        }
 
        for (int i = 0; i < t.length(); ++i) {
            int x = t.charAt(i) - '0';
            if (pos[x].isEmpty()) { //If the digit is not found
                return false;
            }
            for (int j = 0; j < x; ++j) { //Check for smaller digits appearing earlier
                if (!pos[j].isEmpty() && pos[j].peek() < pos[x].peek()) {
                    return false;
                }
            }
            pos[x].poll(); //Remove the earliest occurrence
        }
 
        return true;
    }
}

The C++ and Go solutions follow a very similar structure, utilizing their respective queue implementations. The core logic remains identical across all languages. The primary difference lies in the syntax and specific data structure usage.