2434: Using-a-Robot-to-Print-the-Lexicographically-Smallest-String
Medium

table of contents

The logic for this question is quite straightforward if you ask the right questions.

Since we can only write a character onto the paper if it is the last character of string t, a question we should ask is:

Now, since we are trying to return the lexicographically smallest string that can be written on the paper, the answer is simply:

Therefore, we should precalculate what the lowest remaining character is in s at each index value so that we are able to determine whether or not we should write the last letter of t onto the paper or not.

Finally, once there are no letters remaining in s, we can simply write all the last letters of t onto paper, giving us the lexicographically smallest string that can be written on the paper.

code

class Solution {
public:
    string robotWithString(string s) {
        string maxSuffixCharacter = "";
        char mn = s.back(); // tracking minimum letter
        // stack to keep track of
        // 1.) minimum character in the suffix
        // 2.) last index where this holds true
        stack<pair<char, int>> minSuffixCharacter;
        minSuffixCharacter.push({mn, s.size()-1});
        for (int i = s.size()-2; i >= 0; --i) {
            if (mn-'a' > s[i]-'a') {
                mn = s[i];
                minSuffixCharacter.push({mn, i});
            }
        }
        
        string ans = "";
        stack<char> t;
        for (int i = 0; i < s.size()-1; ++i) {
            // check if the minimum character changes
            if (minSuffixCharacter.top().second <= i) {
                minSuffixCharacter.pop();
            }
            t.push(s[i]);
            // while the last letter <= minimum character in suffix,
            //  write to the paper
            while (!t.empty() && t.top() <= minSuffixCharacter.top().first) {
                ans += t.top();
                t.pop();
            }
        }
        t.push(s.back());
        while (!t.empty()) {
            ans += t.top();
            t.pop();
        }
        return ans;
    }
};

complexity

time taken