Scale Engineer

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 <= 105
  • 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.

import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue; class Solution {    public boolean isTransformable(String s, String t) {        // Anagram check        int[] counts = new int[10];        for (char c : s.toCharArray()) {            counts[c - '0']++;        }        for (char c : t.toCharArray()) {            counts[c - '0']--;        }        for (int count : counts) {            if (count != 0) {                return false;            }        }         // Pre-process s to store indices of each digit        List<Queue<Integer>> positions = new ArrayList<>();        for (int i = 0; i < 10; i++) {            positions.add(new LinkedList<>());        }        for (int i = 0; i < s.length(); i++) {            positions.get(s.charAt(i) - '0').add(i);        }         // Greedily build t        for (int i = 0; i < t.length(); i++) {            int digit = t.charAt(i) - '0';            int pos = positions.get(digit).peek();             // Check for smaller blocking digits            for (int smallerDigit = 0; smallerDigit < digit; smallerDigit++) {                if (!positions.get(smallerDigit).isEmpty() && positions.get(smallerDigit).peek() < pos) {                    return false;                }            }                        // Consume the digit            positions.get(digit).poll();        }         return true;    }}

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.

Solutions

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;  }}

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 →

Next problem