# 2434. Using a Robot to Print the Lexicographically Smallest String

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public: string robotWithString(string s) { string ans; vector count(26); stack stack; for (const char c : s) ++count[c - 'a']; for (const char c : s) { stack.push(c); --count[c - 'a']; const char minChar = getMinChar(count); while (!stack.empty() && stack.top() <= minChar) ans += stack.top(), stack.pop(); } while (!stack.empty()) ans += stack.top(), stack.pop(); return ans; } private: char getMinChar(const vector& count) { for (int i = 0; i < 26; ++i) if (count[i]) return 'a' + i; return 'a'; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public String robotWithString(String s) { StringBuilder sb = new StringBuilder(); int[] count = new int[26]; Deque stack = new ArrayDeque<>(); for (final char c : s.toCharArray()) ++count[c - 'a']; for (final char c : s.toCharArray()) { stack.push(c); --count[c - 'a']; final char minChar = getMinChar(count); while (!stack.isEmpty() && stack.peek() <= minChar) sb.append(stack.poll()); } while (!stack.isEmpty()) sb.append(stack.poll()); return sb.toString(); } private char getMinChar(int[] count) { for (int i = 0; i < 26; ++i) if (count[i] > 0) return (char) ('a' + i); return 'a'; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution: def robotWithString(self, s: str) -> str: ans = [] count = collections.Counter(s) stack = [] for c in s: stack.append(c) count[c] -= 1 minChar = self._getMinChar(count) while stack and stack[-1] <= minChar: ans.append(stack.pop()) return ''.join(ans + stack[::-1]) def _getMinChar(self, count: List[int]) -> str: for c in string.ascii_lowercase: if count[c]: return c return 'a'