Problem Link

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.
    <ul>
    	<li>For example, applying the operation on the underlined substring in <code>&quot;1<u>4234</u>&quot;</code> results in <code>&quot;1<u>2344</u>&quot;</code>.</li>
    </ul>
    </li>
    

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


Python3

class Solution:
    def isTransformable(self, s: str, t: str) -> bool:
        N = len(s)
        index = [[] for _ in range(10)]
        count = [0] * 10
 
        for i, x in enumerate(s):
            index[int(x)].append(i)
        
        for x in t:
            d = int(x)
 
            if count[d] >= len(index[d]):
                return False
            
            # loop through 1...d
            # to check if index[k][count[k]] is < index[d][count[d]],
            # which means k is unable to swap with d, due to d is always larger than k
            for k in range(d):
                if count[k] < len(index[k]) and index[k][count[k]] < index[d][count[d]]:
                    return False
                
            count[d] += 1
 
        return True