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:

1. Create a queue for each digit (0-9) to store its appearances in s in order.
2. Iterate through each character in t, If the current character appears in s before any smaller character, then we can't transform s to t. Otherwise, remove the current character's first appearance in s from the corresponding queue.
3. If s can be transformed to t, after iterating all characters in t, 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.