给你一个字符串 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=“” 。
栈+贪心
class Solution {
public:
string robotWithString(string s) {
string ans;
int cnt[26]{}, min = 0;
for(char c : s) ++cnt[c -'a'];
stack<char> st;
for(char c : s){
st.push(c);
--cnt[c - 'a'];
while(min < 25 && cnt[min] == 0) ++min;
while(!st.empty() && st.top() - 'a' <= min){
ans += st.top();
st.pop();
}
}
return ans;
}
};
时间复杂度：O(n+∣Σ∣)，其中 n 为 s 的长度，∣Σ∣ 为字符集合的大小，本题中字符均为小写字母，所以 ∣Σ∣=26。注意到每个字母只会入栈出栈各一次，且 min 只增不减，因此时间复杂度为 O(n+∣Σ∣)。
空间复杂度：O(n+∣Σ∣)。最坏情况下栈需要 O(n) 的空间。
这道题的难点在于我们什么时候要执行操作1和什么时候要执行操作2。我们可以思考，将t想象成一个栈，先进后出，然后当栈顶元素的值，也就是t的末尾的值比字符串s中的任何一个字符都要小的时候，那么我们就要将栈顶元素推入p中，也就是写出来的字符串，这样才能保证最小字典序列。
那么我们该如何判断s字符串的字符都有多少呢？我们采用一个动态数组cnt来计算s中每个存在字符出现的次数。
由于我们最后从s到栈t，一定是经过s.size()次的st.push，然后又只有两种操作，所以我们可以在每次for循环中进行操作一，然后通过while判断进行多少次操作二，交替进行。
我们采用了一个while判断来确定字符串s中当前存在的最小字符是多少， while(min < 25 && cnt[min] == 0) ++min;，由于0代表a，1代表b…说明第一次cnt[min]不为0的时候，就是s的最小字符。
然后我们将t中的栈顶元素和这个最小字符进行比较，如果栈顶元素小于等于这个最小字符，则执行操作二。
