2434. Using a Robot to Print the Lexicographically Smallest String LeetCode Solution

In this guide, you will get 2434. Using a Robot to Print the Lexicographically Smallest String LeetCode Solution with the best time and space complexity. The solution to Using a Robot to Print the Lexicographically Smallest String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Using a Robot to Print the Lexicographically Smallest String solution in C++
4. Using a Robot to Print the Lexicographically Smallest String solution in Java
5. Using a Robot to Print the Lexicographically Smallest String solution in Python
6. Additional Resources

Problem Statement of 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.

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

2434. Using a Robot to Print the Lexicographically Smallest String LeetCode Solution in C++

class Solution {
 public:
  string robotWithString(string s) {
    string ans;
    vector<int> count(26);
    stack<char> 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<int>& count) {
    for (int i = 0; i < 26; ++i)
      if (count[i])
        return 'a' + i;
    return 'a';
  }
};
/* code provided by PROGIEZ */

2434. Using a Robot to Print the Lexicographically Smallest String LeetCode Solution in Java

class Solution {
  public String robotWithString(String s) {
    StringBuilder sb = new StringBuilder();
    int[] count = new int[26];
    Deque<Character> 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.pop());
    }

    while (!stack.isEmpty())
      sb.append(stack.pop());

    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';
  }
}
// code provided by PROGIEZ

2434. Using a Robot to Print the Lexicographically Smallest String LeetCode Solution in Python

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'
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.