Check If String Is Transformable With Substring Sort Operations

Hard

#1458Time: O(N). The anagram check takes O(N). Populating the `positions` data structure takes O(N). The main loop iterates N times. Inside this loop, we have another loop that runs at most 10 times (for digits 0-9). Thus, the work inside the main loop is O(10 * N) = O(N). The total time complexity is linear.Space: O(N), where N is the length of the strings. The `positions` data structure stores a total of N indices. The character count array takes constant space O(1) as there are only 10 digits.

Patterns

Greedy

Algorithms

Sorting

Data structures

String

Prompt

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"

Example 3:

Input: s = "12345", t = "12435"
Output: false

Constraints:

s.length == t.length
1 <= s.length <= 10⁵
s and t consist of only digits.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach refines the greedy strategy by optimizing the search for characters and their blockers. Instead of repeatedly scanning the string s, we pre-process it to store the indices of each character. This allows us to find the position of the next available character and check for blocking characters in constant time (per digit), leading to a much faster overall algorithm.

Algorithm

First, perform an anagram check. If s and t don't have the same character counts, return false.
Pre-process s to store the indices of each digit. An array of queues or lists, positions, is suitable, where positions[d] holds a sorted list of indices where digit d appears in s.
Iterate through t from i = 0 to n-1. Let c be the character t[i].
The greedy strategy dictates we must use the leftmost available occurrence of c from s. We can get its index, j, by looking at the front of the queue positions[c - '0'].
Now, check if this move is valid. For every digit d that is smaller than c (i.e., d < c - '0'), check if its leftmost available occurrence is at an index smaller than j. If !positions[d].isEmpty() and positions[d].peek() < j, it means c is blocked by a smaller digit d. Return false.
If c is not blocked by any smaller digit, the move is valid. We consume this occurrence of c by removing its index from the front of its queue (e.g., positions[c - '0'].poll()).
If the loop completes successfully for all characters of t, return true.

Walkthrough

The core logic remains the same as the naive approach: a character c at index j in s can be moved to the current leftmost position if and only if there are no smaller available characters at indices less than j. The key to optimization is to avoid the O(N) scans in each step.

We can achieve this by pre-computing the locations of all digits. We use an array of queues, say positions, where positions[d] stores all indices of digit d in s in increasing order.

We then iterate through t. For each t[i], we identify the character c = t[i]. The greedy choice is to use the first available c from s, whose index j is at the front of positions[c - '0']. To check if this is a valid move, we must ensure that for any digit d < c - '0', the first available d is not to the left of j. We can quickly check this by peeking at the front of positions[d] for all d < c - '0'. If we find any such blocking character, we return false. Otherwise, the move is valid, and we remove j from its queue (positions[c - '0'].poll()) to mark it as used.

This pre-computation allows all lookups and checks inside the main loop to be very fast, reducing the complexity from quadratic to linear.

1import java.util.ArrayList;2import java.util.LinkedList;3import java.util.List;4import java.util.Queue;5 6class Solution {7    public boolean isTransformable(String s, String t) {8        // Anagram check9        int[] counts = new int[10];10        for (char c : s.toCharArray()) {11            counts[c - '0']++;12        }13        for (char c : t.toCharArray()) {14            counts[c - '0']--;15        }16        for (int count : counts) {17            if (count != 0) {18                return false;19            }20        }21 22        // Pre-process s to store indices of each digit23        List<Queue<Integer>> positions = new ArrayList<>();24        for (int i = 0; i < 10; i++) {25            positions.add(new LinkedList<>());26        }27        for (int i = 0; i < s.length(); i++) {28            positions.get(s.charAt(i) - '0').add(i);29        }30 31        // Greedily build t32        for (int i = 0; i < t.length(); i++) {33            int digit = t.charAt(i) - '0';34            int pos = positions.get(digit).peek();35 36            // Check for smaller blocking digits37            for (int smallerDigit = 0; smallerDigit < digit; smallerDigit++) {38                if (!positions.get(smallerDigit).isEmpty() && positions.get(smallerDigit).peek() < pos) {39                    return false;40                }41            }42            43            // Consume the digit44            positions.get(digit).poll();45        }46 47        return true;48    }49}

Complexity

Time

O(N). The anagram check takes O(N). Populating the `positions` data structure takes O(N). The main loop iterates N times. Inside this loop, we have another loop that runs at most 10 times (for digits 0-9). Thus, the work inside the main loop is O(10 * N) = O(N). The total time complexity is linear.

Space

O(N), where N is the length of the strings. The `positions` data structure stores a total of N indices. The character count array takes constant space O(1) as there are only 10 digits.

Trade-offs

Pros

Highly efficient with a linear time complexity, making it suitable for large inputs.
It is an optimal solution for this problem.

Cons

Requires more complex data structures (array of lists/queues) compared to the naive approach.
Uses more space to store all indices from the original string.

This approach simulates the process of building the target string t from s in a greedy manner. We iterate through t from left to right. For each character t[i], we find its earliest available occurrence in s and check if it can be moved to the current position. A move is possible only if there are no smaller, un-used characters to its left in s that would block it.

Algorithm

First, check if s and t are anagrams. If their character counts don't match, it's impossible to transform s to t, so return false.
Initialize a boolean array used of size n (the length of the strings) to all false. This array will keep track of which characters from s have been used.
Iterate through the target string t from left to right, with index i from 0 to n-1.
For each character t[i], find the first available matching character in s. This means finding the smallest index j such that s[j] == t[i] and used[j] is false.
Once this character s[j] is found, check if it's possible to move it to the current position. A character can be moved left past any larger or equal characters. It is only blocked by smaller characters. Therefore, we must check if there are any unused characters to the left of s[j] that are smaller than it. Iterate from k = 0 to j-1. If we find an index k where used[k] is false and s[k] < s[j], it means s[j] is blocked. The transformation is impossible, so return false.
If s[j] is not blocked, it means we can use it to form t[i]. Mark it as used by setting used[j] = true.
If the loop completes for all characters in t, it means a valid transformation sequence exists. Return true.

Walkthrough

The fundamental observation is that the sorting operation allows smaller characters to move to the left past larger characters, but a character can never move to the left of a character that is smaller than it. This establishes a relative ordering constraint.

This approach greedily constructs t one character at a time. For t[0], we need to find a character in s that can become the first character. Then for t[1], we find a character from the remaining ones in s that can become the second, and so on. The greedy choice is to always use the leftmost available character from s that matches the required character t[i].

To implement this, we first verify that s and t are anagrams. Then, we iterate through t. For each t[i], we scan s to find the first unused character s[j] that equals t[i]. To check if this s[j] can be moved into position, we must ensure no smaller unused character s[k] exists at an index k < j. If such a blocking character exists, the transformation is impossible. Otherwise, we mark s[j] as used and continue to the next character of t.

1import java.util.Arrays;2 3class Solution {4    public boolean isTransformable(String s, String t) {5        // Anagram check6        int[] counts = new int[10];7        for (char c : s.toCharArray()) {8            counts[c - '0']++;9        }10        for (char c : t.toCharArray()) {11            counts[c - '0']--;12        }13        for (int count : counts) {14            if (count != 0) {15                return false;16            }17        }18 19        int n = s.length();20        boolean[] used = new boolean[n];21 22        for (int i = 0; i < n; i++) {23            char targetChar = t.charAt(i);24            int found_j = -1;25 26            // Find the leftmost unused character in s that matches targetChar27            for (int j = 0; j < n; j++) {28                if (!used[j] && s.charAt(j) == targetChar) {29                    found_j = j;30                    break;31                }32            }33 34            // Check for smaller characters to the left of found_j35            for (int k = 0; k < found_j; k++) {36                if (!used[k] && s.charAt(k) < targetChar) {37                    return false; // Blocked by a smaller character38                }39            }40            41            used[found_j] = true;42        }43 44        return true;45    }46}

Complexity

Time

O(N^2), where N is the length of the strings. The outer loop runs N times (for each character in `t`). Inside, we have two nested loops that, in the worst case, scan through `s`. This results in a quadratic time complexity.

Space

O(N), where N is the length of the string. This is for the `used` boolean array to track which characters have been consumed.

Trade-offs

Pros

The logic is straightforward and directly models the constraints of the problem.
It's relatively easy to implement without complex data structures.

Cons

The time complexity is quadratic, which can be too slow for large inputs (like N=10^5).

Solutions

Solution

1class Solution {2public3  boolean isTransformable(String s, String t) {4    Deque<Integer>[] pos = new Deque[10];5    Arrays.setAll(pos, k->new ArrayDeque<>());6    for (int i = 0; i < s.length(); ++i) {7      pos[s.charAt(i) - '0'].offer(i);8    }9    for (int i = 0; i < t.length(); ++i) {10      int x = t.charAt(i) - '0';11      if (pos[x].isEmpty()) {12        return false;13      }14      for (int j = 0; j < x; ++j) {15        if (!pos[j].isEmpty() && pos[j].peek() < pos[x].peek()) {16          return false;17        }18      }19      pos[x].poll();20    }21    return true;22  }23}

1class Solution {2public:3  bool isTransformable(string s, string t) {4    queue<int> pos[10];5    for (int i = 0; i < s.size(); ++i) {6      pos[s[i] - '0'].push(i);7    }8    for (char &c : t) {9      int x = c - '0';10      if (pos[x].empty()) {11        return false;12      }13      for (int j = 0; j < x; ++j) {14        if (!pos[j].empty() && pos[j].front() < pos[x].front()) {15          return false;16        }17      }18      pos[x].pop();19    }20    return true;21  }22};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem