交换一次使 a 字典序严格大于 b

题目描述

给定两个数字字符串 a 和 b，长度不一定相同。你可以对字符串 a 执行至多一次操作：交换 a 中任意两个位置上的字符（也可以不交换）。

操作完成后：

• 如果存在一种操作使 a' 字典序严格大于 b，输出任意一个满足条件的 a'；
• 否则输出 b。

输入格式：

• 第一行一个整数 t（1 <= t <= 1000），表示测试用例数量。
• 接下来 t 行，每行两个字符串 a 和 b，由空格分隔。
• 字符串仅由数字 '0' 到 '9' 组成，长度分别为 len(a) 和 len(b)，可能不同。

输出格式：

• 对于每个测试用例，输出一行，表示结果字符串。

示例

输入：

5
123 456
789 789
100 200
9 10
12 21

输出：

456
987
200
9
21

解释：

• 123 456：a 最大可变为 321，仍 < 456，输出 456。
• 789 789：a 交换首尾得 987 > 789，输出 987。
• 100 200：a 最大仍是 100，< 200，输出 200。
• 9 10：a 无法交换，"9" > "10"（字典序），输出 9。
• 12 21：a 交换得 21，与 b 相等，不满足严格大于，输出 21。

核心思路

关键观察：

• 如果存在某种交换使 a' > b，那么让 a 最大化后的 a_max 也一定 > b；
• 反之，如果 a_max <= b，那么任何 a' 都 <= a_max <= b，不存在满足条件的 a'。

因此，问题等价于：

1. 构造 a 通过至多一次交换能得到的最大字符串 a_max；
2. 若 a_max > b（字典序严格），输出 a_max；否则输出 b。

长度不同不影响这个逻辑：Python 的字符串比较就是字典序比较，直接 a_max > b 即可。

如何构造字典序最大的 a_max？

从左到右找到第一个位置 i，使得 i 后面存在比 a[i] 更大的字符：

• 在 i 后面的所有字符中，选择最大的字符；
• 若有多个相同的最大字符，选择最靠右的那个位置 j（把较小的 a[i] 放到尽量靠后的位置，对字典序影响最小）；
• 交换 a[i] 和 a[j]。

若不存在这样的 i（字符串已非递增），则不做任何交换，a_max = a。

方法：预处理后缀最大位置 + 贪心交换

思路及解法

1. 预处理后缀最大位置：

   • 从右向左遍历 a，令 max_pos[i] 表示 a[i..n-1] 中最大字符的最右位置。
   • 递推：
     • a[i] > a[max_pos[i+1]] → max_pos[i] = i
     • a[i] == a[max_pos[i+1]] → max_pos[i] = max_pos[i+1]（取最右）
     • a[i] < a[max_pos[i+1]] → max_pos[i] = max_pos[i+1]

2. 从左到右找第一个可增大的位置：

   • 找到第一个 i 满足 a[i] < a[max_pos[i]]；
   • 交换 a[i] 和 a[max_pos[i]]，得到 a_max，跳出。

3. 比较并输出：

   • 若 a_max > b（字典序严格），输出 a_max；否则输出 b。

代码

t = int(input())
for _ in range(t):
	a, b = input().split()
	a = list(a)
	n = len(a)

	# 预处理后缀最大位置
    suf_max = list(range(n))
    for i in range(n - 2, -1, -1):
        if a[i] > a[suf_max[i + 1]]:
            suf_max[i] = i
        else:
            suf_max[i] = suf_max[i + 1]

	# 从左到右找第一个可以增大的位置
    for i in range(n):
        if a[i] < a[suf_max[i]]:
            j = suf_max[i]
            a[i], a[j] = a[j], a[i]
            break

	a = ''.join(a)
	# 字典序严格比较（长度不同也适用）
	print(a if a > b else b)

复杂度分析

• 时间复杂度：$O(len(a) + len(b))$ 每个测试用例。预处理后缀最大位置 $O(len(a))$，贪心交换 $O(len(a))$，字符串比较 $O(\min(len(a), len(b)))$。总时间 $O(\sum (len(a)+len(b)))$。
• 空间复杂度：$O(len(a))$，用于存储后缀最大位置数组和字符串列表。

总结

• 核心转化：若存在合法 a' > b，则 a 最大化后的 a_max 也满足；否则不存在。因此只需构造 a_max 再比较。
• 贪心构造 a_max：从左到右找第一个可增大的位置，用后面最大且最靠右的字符交换。
• 长度不同无需特殊处理：Python 字符串比较天然按字典序，长度不同也能正确比较。
• 严格大于：注意条件是 a_max > b，相等时输出 b。

相关题目

• LC 670. 最大交换（给定整数，最多交换一次使数值最大）
• LC 179. 最大数（拼接使数字最大）
• 字典序比较相关题目