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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Using a Robot to Print the Lexicographically Smallest String

Number: 2520

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a string s, you have a robot that manipulates two strings: s (initially given) and an initially empty string t. You can perform two operations:

  1. Remove the first character from s and append it to t.
  2. Remove the last character from t and append it to a result string (written on paper). Your task is to apply these operations until both s and t are empty, and determine the lexicographically smallest string that can be obtained as the result.

Key Insights

  • The process resembles simulating a stack (for string t) where the removal from t behaves like a pop operation.
  • The main challenge is to decide when to move a character from s to t (push) and when to output a character from t (pop) to ensure the smallest lexicographical order.
  • A greedy approach can be used by comparing the top of the stack (last character in t) with the smallest character available in s.
  • Precompute the minimum remaining character for s starting at each index to decide whether to trigger a pop from t.
  • The algorithm runs in O(n) time using a stack for t and an auxiliary array for tracking the minimum characters in s.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s, since each character is processed once. Space Complexity: O(n), for the stack used to simulate t and the additional array that holds the minimum remaining characters in s.

Solution

We use a greedy strategy with a stack to simulate string t. The idea is to push characters from s into the stack and use a precomputed array (or pointer technique) to know the smallest character remaining in s. If the top of the stack is less than or equal to this smallest remaining character, it is safe to pop the stack and append it to the result. This ensures that the final result string is lexicographically smallest. By continuously making the greedy decision to pop from the stack when it guarantees a lower lexicographical order, we efficiently achieve the optimal solution.

Code Solutions

# Python solution using greedy approach with a stack and precomputed minimum character look-ahead.
def robotWithString(s: str) -> str:
    n = len(s)
    # Precompute minimum character from index i to end of s.
    min_from = [''] * n
    min_from[-1] = s[-1]
    for i in range(n-2, -1, -1):
        min_from[i] = min(s[i], min_from[i+1])
    
    result = []
    stack = []
    i = 0
    # Process until all characters from s are pushed and t (stack) is empty.
    while i < n or stack:
        # If there are still characters in s and either stack is empty or the 
        # top of the stack is greater than the smallest character remaining in s,
        # push the next character from s to the stack.
        if i < n and (not stack or stack[-1] > min_from[i]):
            stack.append(s[i])
            i += 1
        else:
            # Otherwise, pop from the stack and add to result.
            result.append(stack.pop())
    
    return "".join(result)

# Example usage:
print(robotWithString("zza"))  # Expected output: "azz"
← Back to All Questions