2434. Using a Robot to Print the Lexicographically Smallest String

MediumStackGreedyHash TableString
Leetcode Link

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:

  1. Take the first character from the string s and append it to the string t that the robot holds.
  2. 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 character a initially, and it is incremented whenever the count for the current mi 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 string ans.
  • 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 onto ans.

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's Counter from the collections module. This lets us know how many times each character appears in s.

    1cnt = 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 stack stk to simulate the behavior of holding the characters from s before they are written to the paper.

    1ans = []
    2stk = []
  • We keep track of the smallest character we have not used up in s. Initially, this is 'a', the smallest possible character.

    1mi = 'a'
  • We then iterate over each character c in our string s:

    • For each character c, we decrement its count in the frequency counter because we are moving it from s to t (simulated by the stack).

      1cnt[c] -= 1
    • We update the mi variable if the character count for mi has reached zero (meaning all of its occurrences have been used), incrementing it to the next character.

      1while mi < 'z' and cnt[mi] == 0:
      2    mi = chr(ord(mi) + 1)
    • The character c is then pushed onto the stack as part of the simulation of moving it from s to t.

      1stk.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 to mi, it is safe to write this character to paper (append it to ans), so we pop it from the stack. This check is done in a while loop because multiple characters might satisfy this condition.

      1while stk and stk[-1] <= mi:
      2    ans.append(stk.pop())
  • Finally, after the loop has processed all characters from s, the stack will be empty, and the list ans 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.

    1return ''.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.

Example 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:

  1. Initialize the frequency counter, the stack (simulating t), and the ans list (simulating the paper).

    1cnt = Counter("cba")  # cnt = {'c': 1, 'b': 1, 'a': 1}
    2ans = []
    3stk = []
    4mi = 'a'  # Smallest character
  2. We iterate over each character in s.

    • For the first character c:

      1cnt['c'] -= 1  # cnt = {'c': 0, 'b': 1, 'a': 1}
      2stk.append('c')  # stk = ['c']

      We don't update mi because cnt['a'] is not zero. The stack's top c is not less than or equal to mi ('a'), so we don't pop from the stack.

    • For the second character b:

      1cnt['b'] -= 1  # cnt = {'c': 0, 'b': 0, 'a': 1}
      2stk.append('b')  # stk = ['c', 'b']

      We now update mi as 'b' has been used up, but mi remains 'a' because cnt['a'] is not zero. Similarly to the previous step, we do not write to ans because stk[-1] (b) is not less than or equal to mi (a).

    • For the third character a:

      1cnt['a'] -= 1  # cnt = {'c': 0, 'b': 0, 'a': 0}
      2stk.append('a')  # stk = ['c', 'b', 'a']

      mi remains 'a' since all characters have been used at least once. Now the condition stk[-1] <= mi holds true, so we write to ans:

      1# We enter the while loop because stk[-1] ('a') is less than or equal to 'a' (mi).
      2ans.append(stk.pop())  # ans = ['a']
      3# We continue in the loop, now 'b' is at the top of the stack and mi is 'a'
      4# Since 'b' is greater than 'a', we exit the loop.

    After steps 1-3, we have two letters in stk, one letter in ans, and mi remains 'a'. The loop ends since we traversed the entire s. We now have remaining characters in our stack, which need to be appended to ans in reverse order (because we pop them from the stack).

    So we pop b and then c from stk, appending each to ans:

    1ans.append(stk.pop())  # ans = ['a', 'b']
    2ans.append(stk.pop())  # ans = ['a', 'b', 'c']
  3. After processing all the characters, we join the ans list to form the result string.

    1return ''.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".

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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:

  1. The construction of the Counter object - This happens once and takes O(n) time, where n is the length of string s, since the Counter has to iterate through all characters in the string.

  2. The first for loop - This loop runs for each character in the string s, hence it iterates n times.

  3. The inner while loop to find the current minimum character mi - Since there are 26 English letters, in the worst case, it might check every character until 'z', taking O(1) time regardless of the size of s as it's not directly dependent on n.

  4. The second inner while loop where elements are popped from stk and added to ans - Each character can be pushed and popped at most once, leading to O(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:

  1. The Counter object cnt - Its space complexity is O(n) in the worst case when all characters in the s are unique.

  2. The list ans - Worst case, this list will contain all characters from s, thus O(n) space.

  3. The list stk - In the worst case, this can also grow to include all characters from s, hence O(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.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫