LeetCode Solutions Blog

Check If String Is Transformable With Substring Sort Operations

Difficulty: Hard

Problem Description

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. Return true if it is possible to transform s into t. Otherwise, return false.

Key Insights

The characters in s and t must be the same; otherwise, transformation is impossible.
The order of characters in t must be achievable by sorting substrings of s.
We can track the positions of each character in both strings and ensure we can rearrange them to match.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (for the count arrays)

Solution

To determine if string s can be transformed into string t, we can follow these steps:

Count the frequency of each digit (0-9) in both strings to ensure they have the same characters.
Use a two-pointer technique to check if we can match the characters of s to t.
Ensure that as we traverse both strings, the characters in s can be rearranged to match the order in t by sorting substrings.

Code Solutions

def isTransformable(s: str, t: str) -> bool:
    if sorted(s) != sorted(t):  # Check if both have same characters
        return False
    
    # Create lists to track positions of each digit
    from collections import deque
    
    # Deques for positions of each digit in s and t
    positions_s = [deque() for _ in range(10)]
    positions_t = [deque() for _ in range(10)]
    
    for i in range(len(s)):
        positions_s[int(s[i])].append(i)
        positions_t[int(t[i])].append(i)
    
    # Check if we can match the characters
    for digit in range(10):
        while positions_t[digit]:
            # If there's a position in t, we need to find the corresponding position in s
            if not positions_s[digit]:  # No more positions in s for this digit
                return False
            pos_t = positions_t[digit].popleft()
            pos_s = positions_s[digit].popleft()
            if pos_s > pos_t:  # If s is ahead of t, we can't make the transformation
                return False
            
    return True