2434

2434. Using a Robot to Print the Lexicographically Smallest String (Medium)

You are given a string s and a robot that currently holds an empty string t. Apply one of the following operations until s and t are both empty:

• Remove the first character of a string s and give it to the robot. The robot will append this character to the string t.
• Remove the last character of a string t and give it to the robot. The robot will write this character on paper.

Return the lexicographically smallest string that can be written on the paper.

 

Example 1:

Input: s = "zza"
Output: "azz"
Explanation: Let p denote the written string.
Initially p="", s="zza", t="".
Perform first operation three times p="", s="", t="zza".
Perform second operation three times p="azz", s="", t="".

Example 2:

Input: s = "bac"
Output: "abc"
Explanation: Let p denote the written string.
Perform first operation twice p="", s="c", t="ba". 
Perform second operation twice p="ab", s="c", t="". 
Perform first operation p="ab", s="", t="c". 
Perform second operation p="abc", s="", t="".

Example 3:

Input: s = "bdda"
Output: "addb"
Explanation: Let p denote the written string.
Initially p="", s="bdda", t="".
Perform first operation four times p="", s="", t="bdda".
Perform second operation four times p="addb", s="", t="".

 

Constraints:

• 1 <= s.length <= 105
• s consists of only English lowercase letters.

Companies: Amazon

Related Topics:
Hash Table, String, Stack, Greedy

Similar Questions:

• Find Permutation (Medium)

Solution 1. Greedy + Stack

After we move a letter from s to t, we determine if we should write it. We write the back of t on paper only if there are no smaller letter in the remaining s.

// OJ: https://leetcode.com/problems/using-a-robot-to-print-the-lexicographically-smallest-string
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    string robotWithString(string s) {
        int N = s.size();
        vector<char> mn(N + 1, 'z');
        for (int i = N - 1; i >= 0; --i) {
            mn[i] = min(mn[i + 1], s[i]);
        }
        stack<char> st;
        string ans;
        for (int i = 0; i < N; ++i) {
            st.push(s[i]);
            while (st.size() && st.top() <= mn[i + 1]) {
                ans.push_back(st.top());
                st.pop();
            }
        }
        while (st.size()) {
            ans.push_back(st.top());
            st.pop();
        }
        return ans;
    }
};