< Back





2434. Using a Robot to Print the Lexicographically Smallest String

This is a pretty contrived question with a poorly written description. I scratched my head on this
one for longer than I wanted to, until I eventually read some solutions. We're essentially
maintaining a monotonic stack and populating our answer stack / string whenever a particular
condition is met - this condition being that the top of the stack's character is less than or equal
to the current minimum value character in the original string.

We need to maintain what characters are remaining in the original string, so we use a Counter()
object to maintain their count. We immediately push the character currently being inspected onto the
stack, and update the count - if it reaches 0 we delete if from the dictionary. We acquire the
minimum value character from the remaining characters, and if the top of the stack is less than or
equal to this character, we pop the stack and append it to the answer string.

We continue this process until we've processed all characters in the original string. If items
remain on the stack, we pop and add them to the answer string.

The solution is as follows:


  class Solution:
      def robotWithString(self, s: str) -> str:
          count, t, p, smallest = Counter(s), [], [], 'a'

          for c in s:
              t.append(c)
              count[c] -= 1

              if count[c] == 0:
                  del count[c]

              if count:
                  smallest = min(count)

              while count and t and smallest >= t[-1]:
                  p.append(t.pop())

          return "".join(p + t[::-1])


_ Time Complexity:

  O(n) - We process each character in the string once.

_ Space Complexity:

  O(n) - We store a count of each character in the original string, and at most the original string
  in the t list.