2434. Using a Robot to Print the Lexicographically Smallest String
Problem Description
In this problem, you are given a string s
and you are to simulate the behavior of a robot that is generating a new string t
with the ultimate goal of writing down the lexicographically smallest string possible onto paper. The robot achieves this by performing operations until both s
and t
are empty. There are two operations possible:
- Take the first character from the string
s
and append it to the stringt
that the robot holds. - Take the last character from the string
t
and write it down on the paper.
The constraints are that you can only write to paper from t
and you can only add to t
from s
. The challenge is to determine the sequence of operations that lead to the smallest possible string on the paper.
Intuition
To arrive at the lexicographically smallest string, we need to write to the paper in a way that prioritizes placing smaller characters before larger ones. However, we are limited by the arrangement of characters in s
and the operations we can perform.
The solution involves keeping track of the minimum(characters in remaining string s
) while processing characters from s
to t
. We use a stack to replicate the behavior of t
, appending characters from s
and popping them when they are ready to be written to the paper. The idea is to always pop the stack and write to the paper whenever the top of the stack has a character that is less than or equal to the current minimum we can still encounter in the remainder of s
.
Here's the approach broken down:
- We use a counter to keep track of the frequency of characters in
s
. - We iterate through
s
, decrementing the count for each character as we go. - We maintain a variable
mi
which is set to the smallest charactera
initially, and it is incremented whenever the count for the currentmi
becomes zero, i.e., we have used all occurrences of the current smallest character. - We push characters onto a stack, and whenever the top character is less than or equal to
mi
(meaning we can write this character without worrying about missing the opportunity to write a smaller character later), we pop it from the stack and append it to the result stringans
. - We repeat the above steps until all characters from
s
have been pushed to the stack and the stack is emptied by writing its characters ontoans
.
The stack (simulating t
) essentially acts as a holding area where characters have to wait if a smaller character can appear later from s
. Only when we're sure that we're at the smallest possible character that is on top of the stack given the future possibilities, we pop it to ans
.
This strategy guarantees that we are writing the smallest possible characters as early as possible without violating the rules of operation, thus achieving a lexicographically smallest result.
Solution Approach
The solution makes use of a stack data structure, a counter to keep track of character frequencies, and a variable to store the smallest character that can still appear in the string s
.
Here's a step-by-step explanation of the implementation:
-
First, we create a frequency counter for the characters in
s
using Python'sCounter
from thecollections
module. This lets us know how many times each character appears ins
.cnt = Counter(s)
-
We initialize an empty list
ans
that will serve as the paper onto which the robot writes the characters. We also initialize a stackstk
to simulate the behavior of holding the characters froms
before they are written to the paper.ans = [] stk = []
-
We keep track of the smallest character we have not used up in
s
. Initially, this is'a'
, the smallest possible character.mi = 'a'
-
We then iterate over each character
c
in our strings
:-
For each character
c
, we decrement its count in the frequency counter because we are moving it froms
tot
(simulated by the stack).cnt[c] -= 1
-
We update the
mi
variable if the character count formi
has reached zero (meaning all of its occurrences have been used), incrementing it to the next character.while mi < 'z' and cnt[mi] == 0: mi = chr(ord(mi) + 1)
-
The character
c
is then pushed onto the stack as part of the simulation of moving it froms
tot
.stk.append(c)
-
We check the stack's top element and compare it with
mi
. If the top (last) character in the stack is less than or equal tomi
, it is safe to write this character to paper (append it toans
), so we pop it from the stack. This check is done in awhile
loop because multiple characters might satisfy this condition.while stk and stk[-1] <= mi: ans.append(stk.pop())
-
-
Finally, after the loop has processed all characters from
s
, the stack will be empty, and the listans
will hold the lexicographically smallest string that the robot could write on the paper. -
The resulting smallest string is obtained by joining the elements of
ans
and returning it.return ''.join(ans)
This algorithm's correctness relies on the fact that at each step, we are writing the smallest possible character to the paper. Using the stack allows us to temporarily hold characters that might not be optimal to write immediately and wait until we are certain no smaller character will come before them.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example to illustrate the solution approach.
Suppose we are given the following string s
: "cba"
.
Now, let's walk through the solution:
-
Initialize the frequency counter, the stack (simulating
t
), and theans
list (simulating the paper).cnt = Counter("cba") # cnt = {'c': 1, 'b': 1, 'a': 1} ans = [] stk = [] mi = 'a' # Smallest character
-
We iterate over each character in
s
.-
For the first character
c
:cnt['c'] -= 1 # cnt = {'c': 0, 'b': 1, 'a': 1} stk.append('c') # stk = ['c']
We don't update
mi
becausecnt['a']
is not zero. The stack's topc
is not less than or equal tomi
('a'), so we don't pop from the stack. -
For the second character
b
:cnt['b'] -= 1 # cnt = {'c': 0, 'b': 0, 'a': 1} stk.append('b') # stk = ['c', 'b']
We now update
mi
as 'b' has been used up, butmi
remains 'a' becausecnt['a']
is not zero. Similarly to the previous step, we do not write toans
becausestk[-1]
(b
) is not less than or equal tomi
(a
). -
For the third character
a
:cnt['a'] -= 1 # cnt = {'c': 0, 'b': 0, 'a': 0} stk.append('a') # stk = ['c', 'b', 'a']
mi
remains 'a' since all characters have been used at least once. Now the conditionstk[-1] <= mi
holds true, so we write toans
:# We enter the while loop because stk[-1] ('a') is less than or equal to 'a' (mi). ans.append(stk.pop()) # ans = ['a'] # We continue in the loop, now 'b' is at the top of the stack and mi is 'a' # Since 'b' is greater than 'a', we exit the loop.
After steps 1-3, we have two letters in
stk
, one letter inans
, andmi
remains 'a'. The loop ends since we traversed the entires
. We now have remaining characters in our stack, which need to be appended toans
in reverse order (because we pop them from the stack).So we pop
b
and thenc
fromstk
, appending each toans
:ans.append(stk.pop()) # ans = ['a', 'b'] ans.append(stk.pop()) # ans = ['a', 'b', 'c']
-
-
After processing all the characters, we join the
ans
list to form the result string.return ''.join(ans) # 'abc'
This example demonstrates how the given solution approach results in the lexicographically smallest string by strategically moving characters from s
to t
(stack stk
) and then deciding the right time to pop them onto the paper (ans
). The final output of this process is the string "abc"
, which is the smallest possible arrangement of the given string "cba"
.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def robotWithString(self, s: str) -> str:
5 # Counter to keep track of how many of each character are left in the string
6 char_count = Counter(s)
7
8 # Output list to store the characters for the final result
9 result = []
10
11 # Stack to simulate the robot's hand
12 stack = []
13
14 # Variable to keep track of the smallest character not exhausted in the string
15 min_char = 'a'
16
17 # Iterate over the characters in the string
18 for char in s:
19 # Decrement the count for the current character
20 char_count[char] -= 1
21
22 # Update the smallest character ('min_char') if the current one runs out
23 while min_char < 'z' and char_count[min_char] == 0:
24 min_char = chr(ord(min_char) + 1)
25
26 # Append the current character to the stack (robot's hand)
27 stack.append(char)
28
29 # Append characters to the result from the stack if they are smaller
30 # or equal to 'min_char'. This ensures the lexicographically smallest
31 # result possible at each step.
32 while stack and stack[-1] <= min_char:
33 result.append(stack.pop())
34
35 # Join the list of characters to form the final string result
36 return ''.join(result)
37
1class Solution {
2 public String robotWithString(String s) {
3 int[] charCount = new int[26]; // Holds the count of each character in the string
4
5 // Increment the count for each character in the string
6 for (char ch : s.toCharArray()) {
7 charCount[ch - 'a']++;
8 }
9
10 StringBuilder answer = new StringBuilder(); // For building the final string
11 Deque<Character> stack = new ArrayDeque<>(); // To keep track of characters for processing
12 char minChar = 'a'; // To keep track of the smallest character that hasn't been used up
13
14 // Iterate through all characters in the string
15 for (char ch : s.toCharArray()) {
16 charCount[ch - 'a']--; // Decrease the count as we process each char
17
18 // Update the minChar to the next available smallest character
19 while (minChar < 'z' && charCount[minChar - 'a'] == 0) {
20 minChar++;
21 }
22
23 stack.push(ch); // Add current character to the stack
24
25 // Pop characters from the stack if they are smaller or equal to the current minChar
26 while (!stack.isEmpty() && stack.peek() <= minChar) {
27 answer.append(stack.pop());
28 }
29 }
30
31 return answer.toString();
32 }
33}
34
1#include <string>
2#include <vector>
3
4class Solution {
5public:
6 // Method that takes a string s and outputs a string based on certain logic
7 string robotWithString(string s) {
8 int charCount[26] = {0}; // Array to keep track of each character's frequency
9
10 // Count the frequency of each character in the input string
11 for (char ch : s) {
12 ++charCount[ch - 'a'];
13 }
14
15 char minChar = 'a'; // Variable to keep track of the smallest character not used up
16 string stack; // Use a string as a stack to keep track of characters
17 string answer; // The resulting string that we'll build
18
19 // Iterate over each character in the input string
20 for (char ch : s) {
21 // Decrement the count of the current character,
22 // since we're going to process it
23 --charCount[ch - 'a'];
24
25 // Find the smallest character that still has remaining occurrences
26 while (minChar < 'z' && charCount[minChar - 'a'] == 0) {
27 ++minChar;
28 }
29
30 // Push the current character onto the stack
31 stack.push_back(ch);
32
33 // While the stack is not empty and the top of the stack is less than or equal
34 // to the smallest character not used up, append it to the answer and pop it from the stack
35 while (!stack.empty() && stack.back() <= minChar) {
36 answer.push_back(stack.back());
37 stack.pop_back();
38 }
39 }
40
41 // Return the constructed answer string
42 return answer;
43 }
44};
45
1function robotWithString(s: string): string {
2 // Initialize an array to keep count of each character's occurrences
3 let characterCount = new Array(128).fill(0);
4
5 // Counting occurrences of each character in the string
6 for (let character of s) {
7 characterCount[character.charCodeAt(0)] += 1;
8 }
9
10 // Initialize with the charCode of 'a', intending to find the smallest lexicographical character
11 let minCharCodeIndex = 'a'.charCodeAt(0);
12
13 // The output string will be constructed into this array
14 let resultArray = [];
15
16 // Use a stack to keep track of characters processed
17 let charStack = [];
18
19 // Process each character in the given string
20 for (let character of s) {
21 // Decrease the count for this character as it is being processed
22 characterCount[character.charCodeAt(0)] -= 1;
23
24 // Find the next character that still has occurrences left
25 while (minCharCodeIndex <= 'z'.charCodeAt(0) && characterCount[minCharCodeIndex] == 0) {
26 minCharCodeIndex += 1;
27 }
28
29 // Push the current character onto the stack
30 charStack.push(character);
31
32 // As long as the stack is not empty and the last character on the stack is less
33 // or equal to the current minimum, add it to the result array
34 while (charStack.length > 0 && charStack[charStack.length - 1].charCodeAt(0) <= minCharCodeIndex) {
35 resultArray.push(charStack.pop());
36 }
37 }
38
39 // Join the result array into a string and return
40 return resultArray.join('');
41}
42
Time and Space Complexity
Time Complexity
The given Python function robotWithString
has several key operations contributing to its time complexity:
-
The construction of the
Counter
object - This happens once and takesO(n)
time, wheren
is the length of strings
, since theCounter
has to iterate through all characters in the string. -
The first
for
loop - This loop runs for each character in the strings
, hence it iteratesn
times. -
The inner
while
loop to find the current minimum charactermi
- Since there are 26 English letters, in the worst case, it might check every character until 'z', takingO(1)
time regardless of the size ofs
as it's not directly dependent onn
. -
The second inner
while
loop where elements are popped fromstk
and added toans
- Each character can be pushed and popped at most once, leading toO(n)
operations overall.
Given these, we see that the main complexity comes from the operations linked directly to the length of s
. No nested loops are dependent on the size of s
, thus, the overall time complexity is O(n)
.
Space Complexity
Space complexity considerations involve the additional memory used by the algorithm:
-
The
Counter
objectcnt
- Its space complexity isO(n)
in the worst case when all characters in thes
are unique. -
The list
ans
- Worst case, this list will contain all characters froms
, thusO(n)
space. -
The list
stk
- In the worst case, this can also grow to include all characters froms
, henceO(n)
space.
Adding all this up - we have the Counter
, ans
, and stk
all contributing a linear amount of space complexity with respect to the length of string s
. Therefore, the total space complexity is O(n)
, where n
is the length of the string s
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!