---

1585. 检查字符串是否可以通过排序子字符串得到另一个字符串

• 标签：贪心、字符串、排序
• 难度：困难

题目链接

• 1585. 检查字符串是否可以通过排序子字符串得到另一个字符串 - 力扣

题目大意

描述：给定两个字符串 $s$ 和 $t$。每次操作可以选择 $s$ 的一个非空子串并将其中的字符按升序排序。

要求：判断是否可以通过若干次操作将 $s$ 转换为 $t$。

说明：

• $1 \le s.length, t.length \le 10^5$。
• $s$ 和 $t$ 只包含数字 0-9。
• $s.length = t.length$。

示例：

• 示例 1：

输入：s = "84532", t = "34852"
输出：true
解释：你可以按以下操作将 s 转变为 t ：
"84532" （从下标 2 到下标 3）-> "84352"
"84352" （从下标 0 到下标 2） -> "34852"

• 示例 2：

输入：s = "34521", t = "23415"
输出：true
解释：你可以按以下操作将 s 转变为 t ：
"34521" -> "23451"
"23451" -> "23415"

解题思路

思路 1：贪心 + 位置队列

1. 核心思想

对子串进行升序排序，效果是较小的数字向左移动，较大的数字向右移动。这一操作具有以下关键性质：

• 任何数字 $x$ 只能向右移动（当右侧有比它小的数字时，排序会将小数字提到前面，把 $x$ 挤到后面）。
• 反过来，任何数字 $x$ 只能向左移动（当左侧有比它大的数字时）。
• 综合来说：小数字只能左移，大数字只能右移。数字之间的左右相对顺序无法逆转。

由此导出一个核心等价条件：对于每个数字 $d$ 在 $s$ 和 $t$ 中按顺序配对，$s$ 中该 $d$ 的位置之前必须有足够多的比 $d$ 小的数字，来满足 $t$ 中对应位置之前的需求。换言之，对于 $d$ 的每一次出现，在 $s$ 前缀中比 $d$ 小的数字个数 $\ge$ 在 $t$ 对应前缀中的个数。

2. 具体步骤

第 1 步：建立位置队列。用一个长度为 $10$ 的列表 pos，其中 pos[d] 是一个队列，存储数字 d 在 $s$ 中从左到右的所有位置。

第 2 步：判断字符组成是否相同。遍历 $t$ 统计字符频次，同时检查 $s$ 中的对应字符是否足够。一种简洁的方式是结合第 3 步一起做。

第 3 步：从左向右遍历 $t$：

• 对于 $t[j]$，从 pos[int(t[j])] 中弹出最左侧的位置（队列头部）作为 $i$。
• 如果该字符在 $s$ 中不够用（队列为空），返回 False。
• 检查是否有比 $t[j]$ 更小的数字在 $s$ 中出现在位置 $i$ 之前但尚未被匹配。如果有，说明这个更小的数字需要跨过 $d$ 向右移动，但小数字只能左移，矛盾，返回 False。

第 4 步：如果所有字符都匹配成功，返回 True。

3. 正确性证明

设当前处理 $t[j] = d$，从 pos[d] 中取出 $i$ 作为 $d$ 在 $s$ 中的匹配位置。

对于任意 $c < d$，如果 pos[c] 非空且 pos[c][0] < i，说明 $s$ 中位置 $i$ 之前还有一个 $c$ 未被匹配。由于我们是从左向右处理 $t$ 的，所有在 $t$ 中出现在 $j$ 之前的 $c$ 都已经被匹配过了。这个剩余的 $c$ 必须在 $t$ 中出现在 $j$ 之后，即 $c$ 需要越过 $d$ 向右移动。但升序排序只能让小数字左移，不可能让 $c$ 向右跨越 $d$，因此这种情况不可能实现。

反之，如果所有 $c < d$ 的剩余最左位置都 $\ge i$，则 $\forall c < d$，$s[0..i]$ 中 $c$ 的个数 $\ge$ $t[0..j]$ 中 $c$ 的个数，这保证了 $d$ 可以被"推"到其目标位置。

4. 举例说明

以 $s = "84532", t = "34852"$ 为例：

从左向右遍历 $t$：

• $j=0$，$t[0]='3'$ → $s$ 中 $3$ 的位置 $[3]$，弹出 $3$。
  • 检查小于 $3$ 的数字：$2$ 在位置 $4$，$4 \ge 3$，没问题。
• $j=1$，$t[1]='4'$ → $s$ 中 $4$ 的位置 $[1]$，弹出 $1$。
  • 检查小于 $4$ 的数字：$2$ 在位置 $4 (4 \ge 1)$，$3$ 已用完，没问题。
• $j=2$，$t[2]='8'$ → $s$ 中 $8$ 的位置 $[0]$，弹出 $0$。
  • 检查小于 $8$ 的数字：$2$ 在位置 $4 (4 \ge 0)$，$3$、$4$、$5$ 均已用完，没问题。
• $j=3$，$t[3]='5'$ → $s$ 中 $5$ 的位置 $[2]$，弹出 $2$。
  • 检查小于 $5$ 的数字：$2$ 在位置 $4 (4 \ge 2)$，没问题。
• $j=4$，$t[4]='2'$ → $s$ 中 $2$ 的位置 $[4]$，弹出 $4$。
  • 检查小于 $2$ 的数字：$0$、$1$ 均无剩余，没问题。

全部匹配成功，返回 True。

以 $s = "12345", t = "54321"$ 为例（显然不可能，因为 $5$ 无法移动到首位）：

从左向右遍历 $t$：

• $j=0$，$t[0]='5'$ → $s$ 中 $5$ 的位置 $[4]$，弹出 $4$。
  • 检查小于 $5$ 的数字：$1$ 在位置 $0$，$0 < 4$，$1$ 无法向右跨过 $5$，返回 False。

5. 关键原理总结

• 升序排序的效果等价于：小数字左移，大数字右移。
• 按从左到右的顺序匹配 $t$ 中的每个数字，取 $s$ 中该数字最靠左的剩余位置。
• 对于数字 $d$，如果某个更小的数字出现在 $s$ 的匹配位置之前却尚未被匹配，则该更小数字需要向右跨过 $d$，不可能实现。
• 上述条件等价于前缀约束：$\forall c < d$，$count_c(s[0..i]) \ge count_c(t[0..j])$。

思路 1：代码

from collections import deque

class Solution:
    def isTransformable(self, s: str, t: str) -> bool:
        # 0-9 每个数字的位置队列
        pos = [deque() for _ in range(10)]
        for i, ch in enumerate(s):
            pos[int(ch)].append(i)

        # 从左向右遍历 t
        for ch in t:
            d = int(ch)
            if not pos[d]:
                return False
            i = pos[d].popleft()  # 取最左侧的匹配位置

            # 检查是否有更小的数字在 i 之前尚未被匹配
            # 如果有，该小数字需向右跨过 d，不可能
            for smaller in range(d):
                if pos[smaller] and pos[smaller][0] < i:
                    return False

        return True

思路 1：复杂度分析

• 时间复杂度：$O(n \times 10) = O(n)$，每次检查最多遍历 9 个更小的数字队列头部。
• 空间复杂度：$O(n)$，存储每个数字的位置队列。

---

思路 2：前缀计数验证

1. 核心思想

思路 1 的队列方法本质上是逐位验证前缀约束。也可以直接统计前缀中的数字分布来验证。

2. 算法步骤

预处理：构建 $s$ 和 $t$ 每个位置上比当前数字小的数字个数。

验证：对于 $t$ 中的每个位置 $j$ 和数字 $d = t[j]$，找到 $s$ 中对应顺序的 $d$ 的位置 $i$，验证在 $i$ 和 $j$ 之前，每个比 $d$ 小的数字 $c$ 在 $s$ 中的个数 $\ge$ 在 $t$ 中的个数。

这种方法与思路 1 本质相同，但思路 1 的队列实现更简洁，不需要额外的前缀数组。