1585. Check If String Is Transformable With Substring Sort Operations LeetCode Solution
In this guide, you will get 1585. Check If String Is Transformable With Substring Sort Operations LeetCode Solution with the best time and space complexity. The solution to Check If String Is Transformable With Substring Sort Operations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Check If String Is Transformable With Substring Sort Operations
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.
For example, applying the operation on the underlined substring in “14234” results in “12344”.
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”
s.length == t.length
1 <= s.length <= 105
s and t consist of only digits.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1585. Check If String Is Transformable With Substring Sort Operations LeetCode Solution in C++
class Solution {
public:
bool isTransformable(string s, string t) {
if (getCount(s) != getCount(t))
return false;
vector<queue<int>> positions(10);
for (int i = 0; i < s.length(); ++i)
positions[s[i] - '0'].push(i);
// For each digit in `t`, check if we can put this digit in `s` at the same
// position as `t`. Ensure that all the left digits are equal to or greater
// than it. This is because the only operation we can perform is sorting in
// ascending order. If there is a digit to the left that is smaller than it,
// we can never move it to the same position as in `t`. However, if all the
// digits to its left are equal to or greater than it, we can move it one
// position to the left until it reaches the same position as in `t`.
for (const char c : t) {
const int d = c - '0';
const int front = positions[d].front();
positions[d].pop();
for (int smaller = 0; smaller < d; ++smaller)
if (!positions[smaller].empty() && positions[smaller].front() < front)
return false;
}
return true;
}
private:
vector<int> getCount(const string& s) {
vector<int> count(10);
for (const char c : s)
++count[c - '0'];
return count;
}
}; /* code provided by PROGIEZ */
1585. Check If String Is Transformable With Substring Sort Operations LeetCode Solution in Java
class Solution {
public boolean isTransformable(String s, String t) {
if (!Arrays.equals(getCount(s), getCount(t)))
return false;
Queue<Integer>[] positions = new Queue[10];
for (int i = 0; i < 10; i++)
positions[i] = new LinkedList<>();
for (int i = 0; i < s.length(); i++)
positions[s.charAt(i) - '0'].offer(i);
// For each digit in `t`, check if we can put this digit in `s` at the same
// position as `t`. Ensure that all the left digits are equal to or greater
// than it. This is because the only operation we can perform is sorting in
// ascending order. If there is a digit to the left that is smaller than it,
// we can never move it to the same position as in `t`. However, if all the
// digits to its left are equal to or greater than it, we can move it one
// position to the left until it reaches the same position as in `t`.
for (final char c : t.toCharArray()) {
final int d = c - '0';
final int front = positions[d].poll();
for (int smaller = 0; smaller < d; ++smaller)
if (!positions[smaller].isEmpty() && positions[smaller].peek() < front)
return false;
}
return true;
}
private int[] getCount(String s) {
int[] count = new int[10];
for (char c : s.toCharArray())
count[c - '0']++;
return count;
}
} // code provided by PROGIEZ
1585. Check If String Is Transformable With Substring Sort Operations LeetCode Solution in Python
class Solution:
def isTransformable(self, s: str, t: str) -> bool:
if collections.Counter(s) != collections.Counter(t):
return False
positions = [collections.deque() for _ in range(10)]
for i, c in enumerate(s):
positions[int(c)].append(i)
# For each digit in `t`, check if we can put this digit in `s` at the same
# position as `t`. Ensure that all the left digits are equal to or greater
# than it. This is because the only operation we can perform is sorting in
# ascending order. If there is a digit to the left that is smaller than it,
# we can never move it to the same position as in `t`. However, if all the
# digits to its left are equal to or greater than it, we can move it one
# position to the left until it reaches the same position as in `t`.
for c in t:
d = int(c)
front = positions[d].popleft()
for smaller in range(d):
if positions[smaller] and positions[smaller][0] < front:
return False
return True # code by PROGIEZ
