We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check If String Is Transformable With Substring Sort Operations

Number: 1707

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given two numeric strings s and t, determine if it is possible to transform s into t by repeatedly choosing any non-empty substring of s and sorting that substring in ascending order. The operation can be applied any number of times.

Key Insights

  • The operation only sorts substrings in ascending order, so relative order among identical or larger digits cannot be arbitrarily reversed.
  • Both strings must have the same multiset of characters; otherwise, transformation is impossible.
  • For each occurrence of a digit in t, the leftmost available occurrence of that same digit in s must be “free” – meaning there should be no smaller digit located before it that hasn’t been used yet.
  • A greedy approach can be used by precomputing the positions of every digit in s, then processing t sequentially while ensuring no lower digit is available earlier than the chosen index.

Space and Time Complexity

Time Complexity: O(n) – Each character in s and t is processed and for each t we check at most 10 digits. Space Complexity: O(n) – Storing indices for each occurrence of digits in s.

Solution

The solution first verifies that s and t have the same frequency of digits. Then, for each digit from t, we use a queue (or list) to store and retrieve the indices of that digit in s in order. When processing a digit c from t, we check its first available occurrence in s. Before confirming the match, we ensure that no smaller digit has an available index that appears before this chosen index; if one does, then it would have been possible to move that smaller digit further left than c, violating the sorted order requirement. If all checks pass through the entire string t, the transformation is possible.

Code Solutions

# Python solution for checking string transformability using substring sort operations

from collections import deque

def isTransformable(s: str, t: str) -> bool:
    # If frequency counts do not match, transformation is impossible.
    if sorted(s) != sorted(t):
        return False

    # Build a dictionary mapping each digit to a queue of its indices in s
    pos = {str(d): deque() for d in range(10)}
    for idx, char in enumerate(s):
        pos[char].append(idx)

    # Process each digit in t
    for char in t:
        if not pos[char]:
            return False  # No occurrence left for char in s
        
        # The index in s for the current occurrence of char
        cur_index = pos[char].popleft()
        
        # Check for any smaller digit available before cur_index
        for smaller in map(str, range(int(char))):
            if pos[smaller] and pos[smaller][0] < cur_index:
                return False
    return True

# Example usage:
#print(isTransformable("84532", "34852"))  # Expected output: True
← Back to All Questions