Today I have done leetcode's June LeetCoding Challenge with cpp.

June LeetCoding Challenge 6

Description

Using a Robot to Print the Lexicographically Smallest String

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.

Solution

class Solution {
public:
  string robotWithString(string s) {
    vector<int> count(26);
    vector<char> st;
    st.reserve(s.length());
    for(auto c : s) {
      count[c - 'a'] += 1;
    }
    int pos = 0;
    string answer;
    answer.reserve(s.length());
    for(int i = 0; i < 26; ++i) {
      while(st.size() && st.back() <= i + 'a') {
        answer.push_back(st.back());
        st.pop_back();
      }
      if(!count[i]) continue;
      while(count[i] && pos < s.length()) {
        if(s[pos] == i + 'a') {
          answer.push_back(i + 'a');
        } else {
          st.push_back(s[pos]);
        }
        count[s[pos] - 'a'] -= 1;
        pos += 1;
      }
    }
    while(st.size()) {
      answer.push_back(st.back());
      st.pop_back();
    }
    return answer;
  }
};

// Accepted
// 62/62 cases passed (43 ms)
// Your runtime beats 78.06 % of cpp submissions
// Your memory usage beats 95.36 % of cpp submissions (28.3 MB)