Skip to content

← leetcode

Using a Robot to Print the Lexicographically Smallest String

· Medium

LeetCode problem 2434

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:

  • for any given character that is present at the end of string t, how do we know if we should write it onto the paper?

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

  • we can write the last letter of t onto paper as long as there are no remaining letters in s that are lexicographically smaller than it

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: O(n) where n denotes the size of the string s
  • Space: O(n)

time taken

  • 7 minutes and 37 seconds?!