Check If String Is Transformable With Substring Sort Operations solution and explanation
Google
7 more videos on this problem
花花酱 LeetCode 1585. Check If String Is Transformable With Substring Sort Operations - 刷题找工作 EP356Hua Hua · 15:33 · 1K views
LeetCode Solutions 1585. Check If String Is Transformable With Substring Sort OperationsAbrar Sher · 22:39 · 751 views
LeetCode 1585. Check If String Is Transformable With Substring Sort OperationsHappy Coding · 33:46 · 690 views
Leetcode 1585. Check If String Is Transformable With Substring Sort OperationsElite Code · 6:18 · 683 views
1585. Check If String Is Transformable With Substring Sort Operations (Leetcode Hard)Programming Live with Larry · 21:36 · 593 views
【每日一题】1585. Check If String Is Transformable With Substring Sort Operations, 9/15/2020Huifeng Guan · 34:35 · 338 views
LeetCode 1585: Check If String Is Transformable With Substring Sort OperationsAlitaCode · 29:41 · 4 views
ข้อ 1585. Check If String Is Transformable With Substring Sort Operations | LeetCodeThakorn Jareonrat · 13:47 · 4 views
The problem
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
sand 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".
- For example, applying the operation on the underlined substring in
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.length1 <= s.length <= 105sandtconsist of only digits.
Approach overview
Problem Overview: You are given two strings s and t consisting of digits. You can repeatedly choose any substring of s and sort it in ascending order. The task is to determine whether these operations can transform s into t.
Approach 1: Greedy Algorithm with Position Tracking (O(n) time, O(n) space)
This approach processes t from left to right and greedily matches each digit with the earliest valid occurrence in s. Maintain queues (or lists) storing indices of each digit 0–9 in s. When you need digit d for the next position in t, pop the earliest index from the queue for d. The key constraint: no smaller digit can appear before this index in s that hasn’t been used yet. A smaller digit would block the transformation because sorting operations cannot move a larger digit ahead of a smaller one that appears earlier. Checking digits 0..d-1 ensures the move is valid. This greedy ordering directly models the restrictions imposed by substring sorting. It works in linear time because each index is processed once.
Approach 2: Index Matching with Character Buckets (O(n) time, O(n) space)
This method groups positions of digits in s into buckets indexed by digit value. While scanning t, you match each character with the next available index from its corresponding bucket. Before accepting that index, verify that no smaller digit bucket has an earlier unused index. If such a digit exists, the transformation would require moving a larger digit ahead of a smaller one, which substring sorting cannot achieve. Conceptually this approach is similar to the greedy solution but emphasizes bucket-based indexing and pointer tracking. The logic focuses on validating ordering constraints across digit groups rather than directly simulating operations.
Both approaches rely on understanding how sorting a substring affects relative order. Sorting can move smaller digits left but cannot move larger digits ahead of smaller ones already positioned earlier. This constraint turns the problem into verifying whether the relative ordering of digits in s can satisfy the target sequence in t. Efficient tracking of indices with queues or buckets avoids repeated scans.
Recommended for interviews: The greedy position-tracking solution is what most interviewers expect. It demonstrates a strong understanding of ordering constraints and uses efficient data structures from string processing and greedy strategy. A brute-force simulation of substring sorting would be far too slow, but discussing why it fails helps show problem intuition before presenting the optimal linear solution.
Approach 1: Greedy Algorithm with Position Tracking
This approach leverages a greedy algorithm while tracking positions of each digit to determine if it's feasible to reorder s to match t. The idea is to attempt building the target string t in a greedy left-to-right fashion by sort operations on substrings of s.
from collections import defaultdict
def isTransformable(s: str, t: str) -> bool:
pos = defaultdict(list)
for idx, char in enumerate(s):
pos[int(char)].append(idx)
indices = [0] * 10
for char in t:
digit = int(char)
if indices[digit] >= len(pos[digit]):
return False
for d in range(digit):
if indices[d] < len(pos[d]) and pos[d][indices[d]] < pos[digit][indices[digit]]:
return False
indices[digit] += 1
return Trueimport java.util.ArrayList;
import java.util.List;
public class Solution {
public boolean isTransformable(String s, String t) {
int n = s.length();
List<Integer>[] pos = new ArrayList[10];
for (int i = 0; i < 10; i++) {
pos[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++) {
pos[s.charAt(i) - '0'].add(i);
}
int[] indices = new int[10];
for (int i = 0; i < n; i++) {
int digit = t.charAt(i) - '0';
if (indices[digit] >= pos[digit].size()) {
return false;
}
for (int d = 0; d < digit; d++) {
if (indices[d] < pos[d].size() && pos[d].get(indices[d]) < pos[digit].get(indices[digit])) {
return false;
}
}
indices[digit]++;
}
return true;
}
}#include <iostream>
#include <vector>
using namespace std;
bool isTransformable(string s, string t) {
int n = s.size();
vector<vector<int>> pos(10);
for (int i = 0; i < n; ++i) {
pos[s[i] - '0'].push_back(i);
}
vector<int> indices(10, 0);
for (int i = 0; i < n; ++i) {
int digit = t[i] - '0';
if (indices[digit] >= pos[digit].size()) {
return false;
}
for (int d = 0; d < digit; ++d) {
if (indices[d] < pos[d].size() && pos[d][indices[d]] < pos[digit][indices[digit]]) {
return false;
}
}
++indices[digit];
}
return true;
}function isTransformable(s, t) {
const pos = Array.from({ length: 10 }, () => []);
for (let i = 0; i < s.length; i++) {
pos[s[i] - '0'].push(i);
}
const indices = Array(10).fill(0);
for (let i = 0; i < t.length; i++) {
const digit = t[i] - '0';
if (indices[digit] >= pos[digit].length) {
return false;
}
for (let d = 0; d < digit; d++) {
if (indices[d] < pos[d].length && pos[d][indices[d]] < pos[digit][indices[digit]]) {
return false;
}
}
indices[digit]++;
}
return true;
}#include <stdbool.h>
#include <string.h>
bool isTransformable(char *s, char *t) {
int n = strlen(s);
int pos[10][n];
int size[10] = {0};
for (int i = 0; i < n; ++i) {
pos[s[i] - '0'][size[s[i] - '0']++] = i;
}
int indices[10] = {0};
for (int i = 0; i < n; ++i) {
int digit = t[i] - '0';
if (indices[digit] >= size[digit]) {
return false;
}
for (int d = 0; d < digit; ++d) {
if (indices[d] < size[d] && pos[d][indices[d]] < pos[digit][indices[digit]]) {
return false;
}
}
++indices[digit];
}
return true;
}using System;
using System.Collections.Generic;
public class Solution {
public bool IsTransformable(string s, string t) {
int n = s.Length;
List<int>[] pos = new List<int>[10];
for (int i = 0; i < 10; i++) {
pos[i] = new List<int>();
}
for (int i = 0; i < n; i++) {
pos[s[i] - '0'].Add(i);
}
int[] indices = new int[10];
for (int i = 0; i < n; i++) {
int digit = t[i] - '0';
if (indices[digit] >= pos[digit].Count) {
return false;
}
for (int d = 0; d < digit; d++) {
if (indices[d] < pos[d].Count && pos[d][indices[d]] < pos[digit][indices[digit]]) {
return false;
}
}
indices[digit]++;
}
return true;
}
}This Python solution uses defaultdict to store and keep track of the positions where each digit appears in s. The approach checks the relative order of digits to form t via allowed sort operations.
Time Complexity: O(n), Space Complexity: O(n) where n is the length of the string.
Approach 2: Index Matching with Character Buckets
This method uses index matching along with character buckets to determine if s can be reconfigured to t. It uses frequency elements of characters to check if transformation pathways respect substring sort operations.
def characterBuckets(s: str, t: str) -> bool:
chars_s, chars_t = [0] * 10, [0] * 10
for a, b in zip(s, t):
chars_s[int(a)] += 1
chars_t[int(b)] += 1
if any(cs > ct for cs, ct in zip(chars_s, chars_t)):
return False
return Truepublic class Solution {
public boolean characterBuckets(String s, String t) {
int n = s.length();
int[] chars_s = new int[10], chars_t = new int[10];
for (int i = 0; i < n; i++) {
chars_s[s.charAt(i) - '0']++;
chars_t[t.charAt(i) - '0']++;
for (int j = 0; j < 10; j++) {
if (chars_s[j] > chars_t[j]) {
return false;
}
}
}
return true;
}
}#include <iostream>
#include <vector>
using namespace std;
bool characterBuckets(string s, string t) {
int n = s.size();
vector<int> chars_s(10, 0), chars_t(10, 0);
for (int i = 0; i < n; ++i) {
chars_s[s[i] - '0']++;
chars_t[t[i] - '0']++;
for (int j = 0; j < 10; ++j) {
if (chars_s[j] > chars_t[j]) {
return false;
}
}
}
return true;
}function characterBuckets(s, t) {
const chars_s = Array(10).fill(0), chars_t = Array(10).fill(0);
for (let i = 0; i < s.length; i++) {
chars_s[s[i] - '0']++;
chars_t[t[i] - '0']++;
for (let j = 0; j < 10; j++) {
if (chars_s[j] > chars_t[j]) {
return false;
}
}
}
return true;
}#include <stdbool.h>
#include <string.h>
bool characterBuckets(char *s, char *t) {
int n = strlen(s);
int chars_s[10] = {0}, chars_t[10] = {0};
for (int i = 0; i < n; ++i) {
chars_s[s[i] - '0']++;
chars_t[t[i] - '0']++;
if (strcmp((char *)chars_s, (char *)chars_t) > 0) {
return false;
}
}
return true;
}using System;
public class Solution {
public bool CharacterBuckets(string s, string t) {
int[] chars_s = new int[10], chars_t = new int[10];
for (int i = 0; i < s.Length; i++) {
chars_s[s[i] - '0']++;
chars_t[t[i] - '0']++;
for (int j = 0; j < 10; j++) {
if (chars_s[j] > chars_t[j]) {
return false;
}
}
}
return true;
}
}This Python solution maintains two lists for counting occurrences of each digit in s and t, verifying conditions for owning elements to form t.
Time Complexity: O(n), Space Complexity: O(1) due to constant size lists for character tracking.
Approach 3: Bubble Sort
The problem is essentially equivalent to determining whether any substring of length 2 in string s can be swapped using bubble sort to obtain t.
Therefore, we use an array pos of length 10 to record the indices of each digit in string s, where pos[i] represents the list of indices where digit i appears, sorted in ascending order.
Next, we iterate through string t. For each character t[i] in t, we convert it to the digit x. We check if pos[x] is empty. If it is, it means that the digit in t does not exist in s, so we return false. Otherwise, to swap the character at the first index of pos[x] to index i, all indices of digits less than x must be greater than or equal to the first index of pos[x]. If this condition is not met, we return pos[x]false. Otherwise, we pop the first index from and continue iterating through string t.
After the iteration, we return true.
The time complexity is O(n times C), and the space complexity is O(n). Here, n is the length of string s, and C$ is the size of the digit set, which is 10 in this problem.
func isTransformable(s string, t string) bool {
pos := [10][]int{}
for i, c := range s {
pos[c-'0'] = append(pos[c-'0'], i)
}
for _, c := range t {
x := int(c - '0')
if len(pos[x]) == 0 {
return false
}
for j := 0; j < x; j++ {
if len(pos[j]) > 0 && pos[j][0] < pos[x][0] {
return false
}
}
pos[x] = pos[x][1:]
}
return true
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Algorithm with Position Tracking | Time Complexity: O(n), Space Complexity: O(n) where n is the length of the string. |
| Index Matching with Character Buckets | Time Complexity: O(n), Space Complexity: O(1) due to constant size lists for character tracking. |
| Bubble Sort | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Algorithm with Position Tracking | O(n) | O(n) | General case and most interview settings where you must validate ordering constraints efficiently |
| Index Matching with Character Buckets | O(n) | O(n) | When implementing digit buckets or queue-based index tracking for clearer separation by character |
Frequently asked questions
Is Check If String Is Transformable With Substring Sort Operations easy or hard?
LeetCode classifies this problem as Hard because the allowed operation—sorting any substring—creates non‑obvious ordering constraints. The challenge lies in recognizing that smaller digits block larger ones and modeling that restriction using greedy index tracking.
Check If String Is Transformable With Substring Sort Operations Python/Java solution
Python and Java implementations usually maintain an array of queues (size 10) storing indices of digits in the original string. While iterating through the target string, the algorithm pops from the correct queue and checks smaller-digit queues for conflicts, achieving O(n) performance.
How to solve Check If String Is Transformable With Substring Sort Operations in O(n)?
Create 10 queues storing positions of digits in the source string. Traverse the target string and match each digit with the earliest unused index from its queue. Before using that index, confirm that no smaller digit queue contains an earlier index. If such a digit exists, the transformation is impossible; otherwise continue until all characters match.
What is the best approach for Check If String Is Transformable With Substring Sort Operations?
The most effective approach uses a greedy algorithm with position tracking. Store indices of each digit (0–9) from the source string in queues. While scanning the target string, ensure the next required digit appears before any smaller unused digit. This guarantees that substring sorting operations can legally produce the target order.
Is Check If String Is Transformable With Substring Sort Operations asked at Google/Amazon/Meta?
This type of greedy ordering problem appears in interviews at companies such as Google, Amazon, and Meta. It tests understanding of constraints created by sorting operations and the ability to model them using efficient data structures and greedy validation.
What data structure is used in Check If String Is Transformable With Substring Sort Operations?
The typical implementation uses queues or deques to track indices of each digit from 0 to 9. These structures allow efficient retrieval of the earliest unused position while maintaining ordering constraints between digits.
What is the time complexity of Check If String Is Transformable With Substring Sort Operations?
The optimal solution runs in O(n) time with O(n) space. Each character index from the source string is pushed and popped from a queue exactly once, and checking smaller digits involves only 10 possible values (0–9), which is constant overhead.