LeetCode 题解工作台
使用机器人打印字典序最小的字符串
给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串： 删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。 删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。 请你返…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
题目可以转化为，给定一个字符串序列，在借助一个辅助栈的情况下，将其转化为字典序最小的字符串序列。 我们可以用数组 维护字符串 中每个字符的出现次数，用栈 作为题目中的辅助栈，用变量 维护还未遍历到的字符串中最小的字符。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：
- 删除字符串
s的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到t的尾部。 - 删除字符串
t的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。
请你返回纸上能写出的字典序最小的字符串。
示例 1：
输入：s = "zza" 输出："azz" 解释：用 p 表示写出来的字符串。 一开始，p="" ，s="zza" ，t="" 。 执行第一个操作三次，得到 p="" ，s="" ，t="zza" 。 执行第二个操作三次，得到 p="azz" ，s="" ，t="" 。
示例 2：
输入：s = "bac" 输出："abc" 解释：用 p 表示写出来的字符串。 执行第一个操作两次，得到 p="" ，s="c" ，t="ba" 。 执行第二个操作两次，得到 p="ab" ，s="c" ，t="" 。 执行第一个操作，得到 p="ab" ，s="" ，t="c" 。 执行第二个操作，得到 p="abc" ，s="" ，t="" 。
示例 3：
输入：s = "bdda" 输出："addb" 解释：用 p 表示写出来的字符串。 一开始，p="" ，s="bdda" ，t="" 。 执行第一个操作四次，得到 p="" ，s="" ，t="bdda" 。 执行第二个操作四次，得到 p="addb" ，s="" ，t="" 。
提示：
1 <= s.length <= 105s只包含小写英文字母。
解题思路
方法一：贪心 + 栈
题目可以转化为，给定一个字符串序列，在借助一个辅助栈的情况下，将其转化为字典序最小的字符串序列。
我们可以用数组 维护字符串 中每个字符的出现次数，用栈 作为题目中的辅助栈，用变量 维护还未遍历到的字符串中最小的字符。
遍历字符串 ，对于每个字符 ，我们先将字符 在数组 中的出现次数减一，更新 。然后将字符 入栈，此时如果栈顶元素小于等于 ，则循环将栈顶元素出栈，并将出栈的字符加入答案。
遍历结束，返回答案即可。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度，而 为字符集大小，本题中 。
class Solution:
def robotWithString(self, s: str) -> str:
cnt = Counter(s)
ans = []
stk = []
mi = 'a'
for c in s:
cnt[c] -= 1
while mi < 'z' and cnt[mi] == 0:
mi = chr(ord(mi) + 1)
stk.append(c)
while stk and stk[-1] <= mi:
ans.append(stk.pop())
return ''.join(ans)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n + |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates strong understanding of greedy algorithms and stack-based data structures.
- question_mark
They are able to prioritize the lexicographically smallest character efficiently.
- question_mark
The candidate can explain and optimize the trade-offs between time complexity and space usage.
常见陷阱
外企场景- error
Failing to recognize when to choose a character from the stack over s can lead to incorrect results.
- error
Not managing the stack size properly may result in inefficient space usage or wrong lexicographical order.
- error
Misunderstanding the problem's stack-based state management leads to inefficient or incorrect operation sequences.
进阶变体
外企场景- arrow_right_alt
Consider cases where the input string is already sorted or reversed.
- arrow_right_alt
What if additional constraints or operations are introduced, such as multiple robot actions?
- arrow_right_alt
How would the solution change if the problem involved different character sets or larger strings?