Check If String Is Transformable With Substring Sort Operations

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.

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

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