Leetcode 1585. Check If String Is Transformable With Substring Sort Operations
Problem Explanation
This problem asks to check if it is possible to transform the input string s
into the target string t
by sorting non-empty substrings in s
in-place so that the characters are in ascending order. If transformation is possible, return true, otherwise, return false.
A substring should be a contiguous sequence of characters within the string s
.
For instance, assume that the input string s
is "84532" and the target string t
is "34852". We can transform string s
into t
using substring sort operations as:
"84532" (from index 2 to 3) -> "84352"
"84352" (from index 0 to 2) -> "34852"
Therefore, the output is true.
Solution Approach
This problem can be solved using the queue data structure and greedy algorithm.
The key idea is to keep track of the positions of each digit in s
using a queue.
Then for each character in t
, we assert that it could move to the left until it reaches to the same position as in t
.
Our approach works as follow:
- Create a queue for each digit (0-9) to store its appearances in
s
in order. - Iterate through each character in
t
, If the current character appears ins
before any smaller character, then we can't transforms
tot
. Otherwise, remove the current character's first appearance ins
from the corresponding queue. - If
s
can be transformed tot
, after iterating all characters int
, then it's doable.
In detail, first, a map of queues is created for each digit in s
, where each queue stores the indices of the corresponding digit. Then we iterate through the string t
. For each character in t
, pop the first occurrence of this character from its queue and check the first occurrence of the smaller numbers. If a smaller number has a smaller index, return false. Otherwise, continue the process. If we can complete the iteration, then it is doable to transform s
to t
.
Example
Consider s = '84532' and t = '34852'
The queue of indices for each digit in s
is as follows:
0: []
1: []
2: [3]
3: [2]
4: [1]
5: [4]
6: []
7: []
8: [0]
9: []
For t
= '34852', when we deal with '3', we find its first appearance in s
from its queue which is [2], from which we can check the first occurrence of the smaller numbers which are all empty. So we can move '3' to be the first digit in s
. The status for s
would be '34258' and the queue would be:
0: []
1: []
2: [3]
3: []
4: [1]
5: [4]
6: []
7: []
8: [0]
9: []
We could continue the iteration until we transform s
into t
.
Python
1 2python 3from collections import deque 4 5class Solution: 6 def isTransformable(self, s: str, t: str) -> bool: 7 idx, n = [0]*10, len(s) 8 que = [deque() for _ in range(10)] 9 for i in range(n-1, -1, -1): 10 que[int(s[i])].appendleft(i) 11 for c in t: 12 x = int(c) 13 if not que[x]: return False 14 for i in range(x): 15 if que[i] and que[i][0] < que[x][0]: 16 return False 17 que[x].popleft() 18 return True
Java
1 2java 3class Solution { 4 public boolean isTransformable(String s, String t) { 5 int n = s.length(); 6 Queue<Integer>[] pos = new LinkedList[10]; 7 for (int i = 0; i < 10; ++i) 8 pos[i] = new LinkedList<Integer>(); 9 for (int i = 0; i < n; ++i) 10 pos[s.charAt(i) - '0'].offer(i); 11 for (int i = 0; i < n; ++i) { 12 int digit = t.charAt(i) - '0'; 13 if (pos[digit].isEmpty()) 14 return false; 15 for (int j = 0; j < digit; ++j) 16 if (!pos[j].isEmpty() && pos[j].peek() < pos[digit].peek()) 17 return false; 18 pos[digit].poll(); 19 } 20 return true; 21 } 22}
JavaScript
1
2javascript
3var isTransformable = function(s, t) {
4 let n = s.length
5 let pos = Array(10).fill(0).map(() => Array())
6 for(let i=0;i<n;i++){
7 pos[s[i]-'0'].push(i)
8 }
9 for(let i=0;i<n;i++){
10 let digit = t[i] - '0'
11 if(pos[digit].length === 0) return false
12 for(let j=0;j<digit;j++){
13 if(pos[j].length>0 && pos[j][0] < pos[digit][0]){
14 return false
15 }
16 }
17 pos[digit].shift()
18 }
19 return true
20};
C++
1 2cpp 3class Solution { 4public: 5 bool isTransformable(string s, string t) { 6 int n = s.size(); 7 vector<queue<int>> pos(10); 8 for (int i = 0; i < n; ++i) 9 pos[s[i] - '0'].push(i); 10 for (int i = 0; i < n; ++i) { 11 int digit = t[i] - '0'; 12 if (pos[digit].empty()) 13 return false; 14 for (int j = 0; j < digit; ++j) 15 if (!pos[j].empty() && pos[j].front() < pos[digit].front()) 16 return false; 17 pos[digit].pop(); 18 } 19 return true; 20 } 21};
C#
1 2csharp 3public class Solution { 4 public bool IsTransformable(string s, string t) { 5 int n = s.Length; 6 Queue<int>[] pos = new Queue<int>[10]; 7 for (int i = 0; i < 10; ++i) 8 pos[i] = new Queue<int>(); 9 for (int i = 0; i < n; ++i) 10 pos[s[i] - '0'].Enqueue(i); 11 for (int i = 0; i < n; ++i) { 12 int digit = t[i] - '0'; 13 if (pos[digit].Count == 0) 14 return false; 15 for (int j = 0; j < digit; ++j) 16 if (pos[j].Count != 0 && pos[j].Peek() < pos[digit].Peek()) 17 return false; 18 pos[digit].Dequeue(); 19 } 20 return true; 21 } 22}
The algorithms in all languages follow the same logic. The performance is quite good, all pass the existing test cases, and have a time complexity of O(n).Ruby
1 2ruby 3class Solution 4 def is_transformable(s, t) 5 n = s.size 6 pos = Array.new(10) { [] } 7 n.times { |i| pos[s[i].to_i].push(i) } 8 n.times do |i| 9 digit = t[i].to_i 10 return false if pos[digit].empty? 11 (0...digit).each do |j| 12 return false if !pos[j].empty? && pos[j][0] < pos[digit][0] 13 end 14 pos[digit].shift 15 end 16 return true 17 end 18end
Swift
1 2swift 3class Solution { 4 func isTransformable(_ s: String, _ t: String) -> Bool { 5 let n = s.count 6 var pos = [[Int]](repeating: [], count: 10) 7 let arrS = Array(s), arrT = Array(t) 8 for i in 0..<n{ 9 pos[Int(String(arrS[i]))!].append(i) 10 } 11 for i in 0..<n{ 12 let digit = Int(String(arrT[i]))! 13 if pos[digit].isEmpty { return false } 14 for j in 0..<digit{ 15 if !pos[j].isEmpty && pos[j][0] < pos[digit][0] { return false } 16 } 17 pos[digit].removeFirst() 18 } 19 return true 20 } 21}
Go
1 2go 3func isTransformable(s string, t string) bool { 4 n := len(s) 5 pos := make([][]int, 10) 6 for i := 0; i < 10; i++ { 7 pos[i] = make([]int, 0) 8 } 9 for i := 0; i < n; i++ { 10 pos[s[i]-'0'] = append(pos[s[i]-'0'], i) 11 } 12 for i := 0; i < n; i++ { 13 digit := t[i] - '0' 14 if len(pos[digit]) == 0 { 15 return false 16 } 17 for j := 0; j < int(digit); j++ { 18 if len(pos[j]) > 0 && pos[j][0] < pos[digit][0] { 19 return false 20 } 21 } 22 pos[digit] = pos[digit][1:] 23 } 24 return true 25}
In the above solutions, you can see the same greedy approach being used. The only difference is syntax and some language specifics. Each programming language provides different ways to handle strings, lists (arrays), and queues. But the underlying logic remains the same. Once we understand the idea behind the solution, translating it to another language becomes a matter of knowing the syntax and the language-specific properties. For example, 's[i] - '0'' is used to convert a char to an integer in many programming languages. Additionally, functions like .isEmpty, .shift, .pop, .peek are common in some languages to handle queue operations, while in others it will need to be implemented differently.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.