# 1585. Check If String Is Transformable With Substring Sort Operations

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public: bool isTransformable(string s, string t) { if (getCount(s) != getCount(t)) return false; vector> 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 getCount(const string& s) { vector count(10); for (const char c : s) ++count[c - '0']; return count; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public boolean isTransformable(String s, String t) { if (!Arrays.equals(getCount(s), getCount(t))) return false; Queue[] 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 (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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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 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