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:
s and give it to the robot. The robot will append this character to the string t.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 <= 105s consists of only English lowercase letters.The key idea is to use two stacks to simulate the operations. First, iterate through the string s and push each character onto a stack representing t. Also maintain an additional stack that represents the minimum character that can still be taken from s at each point. This helps in deciding when to pop a character from t to the final result string.
At each step, compare the last character of t with the smallest character that can be taken from s. This ensures that characters are added in lexicographical order.
This Python code uses the concept of a stack to simulate the robot operation. A list t_stack simulates the robot's temporary storage, and result accumulates the final string. A helper list min_suffix keeps track of the smallest character from each position to the end of string s. This enables comparisons and decision-making for moving characters.
C++
Time Complexity: O(n) where n is the length of string s, as each operation (push/pop/compare) is O(1) and every character is processed once.
Space Complexity: O(n) due to both t_stack and min_suffix requiring linear space.
In this approach, a priority queue can be used to determine the smallest character that can be popped from either s or t. By maintaining character frequency, this approach can selectively remove characters to ensure the smallest lexicographical order at each step.
This Java code leverages a stack to simulate the process of transferring characters, along with an array to track character frequencies. The loop checks if the smallest character from the priority queue is in tStack or the remaining s to make decisions on which character to move to the resulting string.
JavaScript
Time Complexity: O(n), as each character operation is iterated over a constant number of possibilities.
Space Complexity: O(n) due to the stack and character count arrays.
| Approach | Complexity |
|---|---|
| Greedy Approach with Two Stacks | Time Complexity: O(n) where n is the length of string s, as each operation (push/pop/compare) is O(1) and every character is processed once. Space Complexity: O(n) due to both |
| Character Frequency and Priority Queue | Time Complexity: O(n), as each character operation is iterated over a constant number of possibilities. Space Complexity: O(n) due to the stack and character count arrays. |
K-th Smallest in Lexicographical Order - Leetcode 440 - Python • NeetCodeIO • 15,855 views views
Watch 9 more video solutions →Practice Using a Robot to Print the Lexicographically Smallest String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor