LeetCode 1585. Check If String Is Transformable With Substring Sort Operations Solution in Java, C++, Python & Go | Explanation + Code

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.

Solutions

Solution 1: Bubble Sort

The problem is essentially equivalent to determining whether any substring of length 2 in string s can be swapped using bubble sort to obtain t.

Therefore, we use an array pos of length 10 to record the indices of each digit in string s, where pos[i] represents the list of indices where digit i appears, sorted in ascending order.

Next, we iterate through string t. For each character t[i] in t, we convert it to the digit x. We check if pos[x] is empty. If it is, it means that the digit in t does not exist in s, so we return false. Otherwise, to swap the character at the first index of pos[x] to index i, all indices of digits less than x must be greater than or equal to the first index of pos[x]. If this condition is not met, we return false. Otherwise, we pop the first index frompos[x]and continue iterating through stringt$.

After the iteration, we return true.

The time complexity is O(n × C), and the space complexity is O(n). Here, n is the length of string s, and C is the size of the digit set, which is 10 in this problem.

PythonJavaC++Go

class Solution: def isTransformable(self, s: str, t: str) -> bool: pos = defaultdict(deque) for i, c in enumerate(s): pos[int(c)].append(i) for c in t: x = int(c) if not pos[x] or any(pos[i] and pos[i][0] < pos[x][0] for i in range(x)): return False pos[x].popleft() return True(code-box)

class Solution { public boolean isTransformable(String s, String t) { Deque<Integer>[] pos = new Deque[10]; Arrays.setAll(pos, k -> new ArrayDeque<>()); for (int i = 0; i < s.length(); ++i) { pos[s.charAt(i) - '0'].offer(i); } for (int i = 0; i < t.length(); ++i) { int x = t.charAt(i) - '0'; if (pos[x].isEmpty()) { return false; } for (int j = 0; j < x; ++j) { if (!pos[j].isEmpty() && pos[j].peek() < pos[x].peek()) { return false; } } pos[x].poll(); } return true; } }(code-box)

class Solution { public: bool isTransformable(string s, string t) { queue<int> pos[10]; for (int i = 0; i < s.size(); ++i) { pos[s[i] - '0'].push(i); } for (char& c : t) { int x = c - '0'; if (pos[x].empty()) { return false; } for (int j = 0; j < x; ++j) { if (!pos[j].empty() && pos[j].front() < pos[x].front()) { return false; } } pos[x].pop(); } return true; } };(code-box)

func isTransformable(s string, t string) bool { pos := [10][]int{} for i, c := range s { pos[c-'0'] = append(pos[c-'0'], i) } for _, c := range t { x := int(c - '0') if len(pos[x]) == 0 { return false } for j := 0; j < x; j++ { if len(pos[j]) > 0 && pos[j][0] < pos[x][0] { return false } } pos[x] = pos[x][1:] } return true }(code-box)