LeetCode 1585 - Check If String Is Transformable With Substring Sort Operations

LeetCode Problem 1585

Difficulty: 🔴 Hard
Topics: String, Greedy, Sorting

Solution

Problem Understanding

This problem asks whether we can transform one digit string, s, into another digit string, t, using a special operation. In one operation, we choose any non-empty contiguous substring of s and sort that substring in ascending order.

The important detail is that sorting a substring only moves smaller digits toward the left and larger digits toward the right. A digit can never "jump" past a smaller digit that is positioned before it unless that smaller digit also moves. This creates ordering constraints that determine whether the transformation is possible.

We are given two strings of equal length consisting only of digits '0' through '9'. We must return true if some sequence of substring sorting operations can convert s into t, otherwise return false.

The constraints are large:

• 1 <= n <= 10^5
• Only digits are used

Because the input size can reach one hundred thousand characters, any exponential or quadratic simulation approach will be too slow. We need a near linear time solution.

There are several important observations and edge cases:

• The two strings must contain the same multiset of digits. If one digit appears more times in t than in s, transformation is impossible.
• Digits cannot arbitrarily cross smaller digits. For example, transforming "12345" into "12435" is impossible because digit '4' would need to move left past '3'.
• Repeated digits must be handled carefully. We need to track the exact order in which occurrences are used.
• Since digits are limited to only 0 through 9, we can efficiently maintain positional information for each digit.

Approaches

Brute Force Approach

A brute force solution would attempt to simulate all possible substring sorting operations and search for a sequence that transforms s into t.

One possible implementation would use BFS:

1. Start from string s
2. Generate all strings obtainable by sorting every possible substring
3. Continue exploring until either t is found or all possibilities are exhausted

This approach is theoretically correct because it explores the entire reachable state space. If t is reachable, BFS will eventually find it.

However, this is completely impractical for the given constraints. A string of length n has O(n^2) substrings, and each operation can generate a new string state. The number of reachable states grows explosively, making this infeasible even for small inputs.

Key Insight

Instead of simulating operations, we analyze what substring sorting actually allows.

Sorting a substring in ascending order lets smaller digits move leftward. However, a digit cannot move left past a smaller digit that currently appears before it.

Suppose we want to place digit d from s into its next required position in t.

Before using this occurrence of d, we must ensure that no smaller digit still waiting in s appears earlier than this d. If such a smaller digit exists, then d can never cross it, making the transformation impossible.

This leads to a greedy positional strategy:

• Store the positions of every digit in s
• Process t from left to right
• For each target digit d, use the earliest unused occurrence of d from s
• Before using it, check whether any smaller digit still has an unused occurrence positioned earlier

If yes, transformation is impossible.

If not, we can safely use this occurrence.

Because digits are only 0 through 9, checking smaller digits is constant work.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all reachable string states
Optimal	O(n)	O(n)	Uses queues of digit positions and greedy validation

Algorithm Walkthrough

1. Create a queue for each digit from 0 to 9.

Each queue stores all indices where that digit appears in s. We store them in increasing order because we always want to use the earliest available occurrence first. 2. Traverse the string s.

For every character s[i], append index i to the queue corresponding to that digit. 3. Process the target string t from left to right.

For each digit d in t, we attempt to match it with the earliest unused occurrence of d from s. 4. Check whether digit d still has an unused occurrence available.

If the queue for d is empty, then t requires more occurrences of d than s contains. Return false. 5. Let current_index be the earliest unused occurrence of d.

This is the position we want to move into the next target location. 6. Check all smaller digits.

For every digit smaller from 0 to d - 1:

• If that smaller digit still has an unused occurrence
• And its earliest unused position is before current_index

then transformation is impossible.

This means the current digit would need to cross a smaller digit to move left, which substring sorting cannot accomplish. 7. If no blocking smaller digit exists, consume this occurrence.

Remove the front index from digit d's queue and continue processing. 8. If all digits in t are processed successfully, return true.

Why it works

The algorithm maintains the invariant that digits are consumed in the same relative order they must appear after all valid sorting operations.

A larger digit can move right freely during sorting, but it cannot move left across a smaller digit that still appears earlier in the original string. By checking whether any smaller unused digit blocks the current digit, we exactly capture the only condition that makes transformation impossible.

Because we always consume the earliest available occurrence of each digit, the greedy strategy preserves all future possibilities and never skips a valid configuration.

Python Solution

from collections import deque
from typing import List

class Solution:
    def isTransformable(self, s: str, t: str) -> bool:
        positions = [deque() for _ in range(10)]

        for index, char in enumerate(s):
            digit = int(char)
            positions[digit].append(index)

        for char in t:
            digit = int(char)

            if not positions[digit]:
                return False

            current_index = positions[digit][0]

            for smaller_digit in range(digit):
                if positions[smaller_digit]:
                    if positions[smaller_digit][0] < current_index:
                        return False

            positions[digit].popleft()

        return True

The implementation begins by creating ten queues, one for each digit from 0 to 9. Each queue stores the positions where that digit appears in s.

As we iterate through s, we append indices into the appropriate queue. Since indices are added in order, each queue naturally remains sorted.

Next, we process t character by character. For each digit, we retrieve the earliest unused occurrence from s.

Before consuming that occurrence, we verify that no smaller digit still has an earlier unused position. If such a smaller digit exists, then the current digit cannot legally move ahead of it through substring sorting.

If the check passes, we remove the used occurrence from the queue and continue.

If every character is processed successfully, the transformation is valid.

Go Solution

func isTransformable(s string, t string) bool {
	positions := make([][]int, 10)

	for i, ch := range s {
		digit := int(ch - '0')
		positions[digit] = append(positions[digit], i)
	}

	pointers := make([]int, 10)

	for _, ch := range t {
		digit := int(ch - '0')

		if pointers[digit] >= len(positions[digit]) {
			return false
		}

		currentIndex := positions[digit][pointers[digit]]

		for smaller := 0; smaller < digit; smaller++ {
			if pointers[smaller] < len(positions[smaller]) {
				if positions[smaller][pointers[smaller]] < currentIndex {
					return false
				}
			}
		}

		pointers[digit]++
	}

	return true
}

The Go implementation uses slices instead of deques. Since Go slices do not support efficient front removal, we keep a pointer for each digit indicating the next unused occurrence.

This avoids repeated slice shifting operations and preserves overall linear complexity.

There are no integer overflow concerns because indices are bounded by 10^5.

Worked Examples

Example 1

s = "84532"
t = "34852"

Initial Queues

Digit	Positions
2	[4]
3	[3]
4	[1]
5	[2]
8	[0]

Process Target String

Target Digit	Current Index	Blocking Smaller Digit?	Result
3	3	None	Use index 3
4	1	None	Use index 1
8	0	None	Use index 0
5	2	None	Use index 2
2	4	None	Use index 4

All digits are processed successfully, so the answer is true.

Example 2

s = "34521"
t = "23415"

Initial Queues

Digit	Positions
1	[4]
2	[3]
3	[0]
4	[1]
5	[2]

Process Target String

Target Digit	Current Index	Blocking Smaller Digit?	Result
2	3	None	Use index 3
3	0	None	Use index 0
4	1	None	Use index 1
1	4	None	Use index 4
5	2	None	Use index 2

All digits can be matched legally, so the answer is true.

Example 3

s = "12345"
t = "12435"

Initial Queues

Digit	Positions
1	[0]
2	[1]
3	[2]
4	[3]
5	[4]

Process Target String

Target Digit	Current Index	Blocking Smaller Digit?	Result
1	0	None	Use index 0
2	1	None	Use index 1
4	3	Digit 3 at index 2 blocks it	Return false

Digit 4 cannot move left past digit 3, so transformation is impossible.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each digit occurrence is processed once, and checking smaller digits costs at most 10 operations
Space	O(n)	Position queues store all indices from the input string

The algorithm is linear because each index enters and leaves its digit queue exactly once. The inner loop only iterates through digits 0 to 9, which is constant work.

Test Cases

sol = Solution()

assert sol.isTransformable("84532", "34852") is True  # provided example
assert sol.isTransformable("34521", "23415") is True  # provided example
assert sol.isTransformable("12345", "12435") is False  # blocked by smaller digit

assert sol.isTransformable("1", "1") is True  # single identical digit
assert sol.isTransformable("12", "21") is False  # cannot move 2 before 1
assert sol.isTransformable("21", "12") is True  # sorting entire string works

assert sol.isTransformable("111", "111") is True  # repeated identical digits
assert sol.isTransformable("5522", "2255") is True  # larger digits can move right
assert sol.isTransformable("2255", "5522") is False  # larger digits cannot move left

assert sol.isTransformable("0123456789", "0123456789") is True  # already equal
assert sol.isTransformable("9876543210", "0123456789") is True  # full sorting possible

assert sol.isTransformable("122333", "123233") is False  # ordering conflict
assert sol.isTransformable("312", "123") is True  # valid through sorting
assert sol.isTransformable("123", "321") is False  # impossible ordering

assert sol.isTransformable("001122", "001122") is True  # duplicate digits
assert sol.isTransformable("102345", "012345") is True  # zero can move left

Test Summary

Test	Why
"84532" -> "34852"	Valid complex transformation
"34521" -> "23415"	Multiple valid sorting operations
"12345" -> "12435"	Smaller digit blocks movement
"1" -> "1"	Minimum input size
"12" -> "21"	Impossible swap
"21" -> "12"	Entire string sorting works
"111" -> "111"	Repeated identical digits
"5522" -> "2255"	Large digits moving right
"2255" -> "5522"	Large digits blocked moving left
"9876543210" -> "0123456789"	Full ascending sort
"122333" -> "123233"	Duplicate ordering conflict
"312" -> "123"	Valid reordering
"123" -> "321"	Impossible descending target
"102345" -> "012345"	Zero moving left

Edge Cases

One important edge case occurs when the strings contain repeated digits. A naive implementation might only compare counts of digits and overlook ordering constraints between multiple occurrences. For example, different copies of the same digit must be consumed in the correct order. The queue-based approach handles this naturally by always using the earliest unused occurrence.

Another tricky case is when a larger digit needs to move left across a smaller digit. This is the central impossibility condition of the problem. In "12345" to "12435", digit '4' would need to cross '3', which cannot happen through ascending substring sorts. The algorithm explicitly detects this by checking earlier unused smaller digits.

A third edge case involves strings that are already equal. Some solutions mistakenly attempt unnecessary transformations or overcomplicate the logic. In this implementation, matching digits are simply consumed from their queues without issue, and the algorithm correctly returns true.

A final important case is when one string contains more occurrences of a digit than the other. Even though the problem guarantees equal lengths, digit frequencies may differ. If a required digit queue becomes empty during processing, the algorithm immediately returns false, correctly identifying the mismatch.