We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Using a Robot to Print the Lexicographically Smallest String

Difficulty: Medium

Problem Description

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:

  1. Remove the first character of a string s and give it to the robot. The robot will append this character to the string t.
  2. 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.

Key Insights

  • The problem requires maintaining the order of characters while ensuring the output is the smallest lexicographically.
  • Utilizing a stack (or a similar structure) for string t allows efficient addition and removal of characters.
  • Greedy strategy is essential: always choose the smallest available character to write on paper from t or s.

Space and Time Complexity

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

Solution

To solve the problem, we will use a stack to represent the string t. We will iterate through the string s, pushing characters onto the stack. Whenever we can, we will pop characters from the stack to form the final output string. We will keep track of the smallest character that can be pushed from s to t, and decide when to pop from t to write to the final result.

  1. Initialize an empty stack for t and an empty result list for the final output.
  2. Use a pointer to iterate over s.
  3. Keep a count of remaining characters in s to know how many more characters can be pushed to t.
  4. For each character in s, push it to t and check if the top of t can be written to the output result.
  5. Continue this process until both s and t are empty.

Code Solutions

def robotWithString(s: str) -> str:
    t = []
    result = []
    count = [0] * 26  # Count of characters in s
    for char in s:
        count[ord(char) - ord('a')] += 1

    for char in s:
        t.append(char)  # Push character to t
        count[ord(char) - ord('a')] -= 1  # Decrease count of this character
        # While we can pop from t to result
        while t and (not count[ord(t[-1]) - ord('a')] or t[-1] <= min(filter(lambda x: count[ord(x) - ord('a')] > 0, s))):
            result.append(t.pop())  # Write character to result

    return ''.join(result)
← Back to All Questions