题目大意

给定两个长度相同的数字串 A 和 B（可能包含前导零），且保证 A ≥ B。我们需要通过恰好修改 A 中的 k 个数字，得到一个数字串 C，满足：

1. C 的长度与 A、B 相同
2. C 是由 A 恰好修改 k 个字符得到的
3. C < B
4. 在满足上述条件的情况下，C 要尽可能大

如果不存在这样的 C，输出 -1。

问题分析

这是一个典型的贪心构造问题，需要我们在满足约束条件的情况下构造最优解。

关键观察

1. 目标：构造最大的 C 使得 C < B
2. 约束：必须恰好修改 k 个位置
3. 难点：需要在"尽可能大"和"小于 B"之间找到平衡

解题思路

基本策略是从高位到低位处理，在保证 C < B 的前提下，尽可能让高位数字大。

核心思想：

• 对于每个位置，我们尝试在保证后续能够满足条件的情况下，尽可能选择大的数字
• 需要考虑的因素：
  1. 当前选择的数字是否会导致 C ≥ B
  2. 剩余的修改次数是否足够完成构造
  3. 是否能在后续位置中完成恰好 k 次修改

算法步骤

1. 预处理：找出 A 和 B 第一个不同的位置（分界点）
2. 分类讨论：
   • 如果 A 和 B 完全相同：需要至少修改一个位置来使 C < B
   • 如果 A > B：有更多灵活性
3. 贪心构造：
   • 从高位到低位，对于每个位置尝试：
     • 如果还能保证 C < B，尝试使用尽可能大的数字
     • 确保剩余的修改次数足够完成构造
4. 可行性检查：
   • 检查是否能在恰好 k 次修改的情况下完成构造
   • 检查是否能在后续位置中满足 C < B 的条件

特殊情况处理

• k = 0：如果 A < B 则直接输出 A，否则无解
• A = B：必须至少修改一个位置
• 前导零：需要特别注意，因为题目允许前导零

复杂度分析

• 时间复杂度：O(n)，其中 n 是数字串长度
• 空间复杂度：O(n)

实现提示

1. 使用字符串处理，注意前导零
2. 仔细处理边界情况
3. 注意修改次数的精确计数
4. 使用贪心策略时，要确保后续有足够的修改空间

总结

这道题考察的是在多重约束下的贪心构造能力，需要仔细分析各种情况并设计合适的策略。解决这类问题的关键是找到合适的贪心顺序，并在每一步都确保后续步骤的可行性。