2434. Using a Robot to Print the Lexicographically Smallest String

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:

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

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 <= 10⁵
s consists of only English lowercase letters.

Solutions

Solution 1: Greedy + Stack

Thinking

At \(n\le 10^5\), the paper tape is a stack: a letter must be pushed before it can be printed. For the lexicographically smallest string, pop whenever the top is no larger than the smallest letter still unread.

Count remaining letters and keep the smallest leftover \(\textit{mi}\). Push each character, then pop while the top is \(\le \textit{mi}\).

The problem can be transformed into: given a string sequence, use an auxiliary stack to convert it into the lexicographically smallest string sequence.

We can use an array \(\textit{cnt}\) to maintain the count of each character in string \(s\), use a stack \(\textit{stk}\) as the auxiliary stack mentioned in the problem, and use a variable \(\textit{mi}\) to keep track of the smallest character not yet traversed in the string.

Traverse the string \(s\). For each character \(c\), first decrement its count in the array \(\textit{cnt}\) and update \(\textit{mi}\). Then push \(c\) onto the stack. At this point, if the top element of the stack is less than or equal to \(\textit{mi}\), repeatedly pop the top element from the stack and add it to the answer.

After the traversal, return the answer.

The time complexity is \(O(n + |\Sigma|)\), and the space complexity is \(O(n)\), where \(n\) is the length of the string \(s\) and \(|\Sigma|\) is the size of the character set, which is \(26\) in this problem.

Python3JavaC++GoTypeScriptRust

class Solution:
    def robotWithString(self, s: str) -> str:
        cnt = Counter(s)
        ans = []
        stk = []
        mi = 'a'
        for c in s:
            cnt[c] -= 1
            while mi < 'z' and cnt[mi] == 0:
                mi = chr(ord(mi) + 1)
            stk.append(c)
            while stk and stk[-1] <= mi:
                ans.append(stk.pop())
        return ''.join(ans)

class Solution {
    public String robotWithString(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            ++cnt[c - 'a'];
        }
        StringBuilder ans = new StringBuilder();
        Deque<Character> stk = new ArrayDeque<>();
        char mi = 'a';
        for (char c : s.toCharArray()) {
            --cnt[c - 'a'];
            while (mi < 'z' && cnt[mi - 'a'] == 0) {
                ++mi;
            }
            stk.push(c);
            while (!stk.isEmpty() && stk.peek() <= mi) {
                ans.append(stk.pop());
            }
        }
        return ans.toString();
    }
}

class Solution {
public:
    string robotWithString(string s) {
        int cnt[26] = {0};
        for (char& c : s) ++cnt[c - 'a'];
        char mi = 'a';
        string stk;
        string ans;
        for (char& c : s) {
            --cnt[c - 'a'];
            while (mi < 'z' && cnt[mi - 'a'] == 0) ++mi;
            stk += c;
            while (!stk.empty() && stk.back() <= mi) {
                ans += stk.back();
                stk.pop_back();
            }
        }
        return ans;
    }
};

func robotWithString(s string) string {
    cnt := make([]int, 26)
    for _, c := range s {
        cnt[c-'a']++
    }
    mi := byte('a')
    stk := []byte{}
    ans := []byte{}
    for i := range s {
        cnt[s[i]-'a']--
        for mi < 'z' && cnt[mi-'a'] == 0 {
            mi++
        }
        stk = append(stk, s[i])
        for len(stk) > 0 && stk[len(stk)-1] <= mi {
            ans = append(ans, stk[len(stk)-1])
            stk = stk[:len(stk)-1]
        }
    }
    return string(ans)
}

function robotWithString(s: string): string {
    const cnt = new Map<string, number>();
    for (const c of s) {
        cnt.set(c, (cnt.get(c) || 0) + 1);
    }
    const ans: string[] = [];
    const stk: string[] = [];
    let mi = 'a';
    for (const c of s) {
        cnt.set(c, (cnt.get(c) || 0) - 1);
        while (mi < 'z' && (cnt.get(mi) || 0) === 0) {
            mi = String.fromCharCode(mi.charCodeAt(0) + 1);
        }
        stk.push(c);
        while (stk.length > 0 && stk[stk.length - 1] <= mi) {
            ans.push(stk.pop()!);
        }
    }
    return ans.join('');
}

impl Solution {
    pub fn robot_with_string(s: String) -> String {
        let mut cnt = [0; 26];
        for &c in s.as_bytes() {
            cnt[(c - b'a') as usize] += 1;
        }

        let mut ans = Vec::with_capacity(s.len());
        let mut stk = Vec::new();
        let mut mi = 0;

        for &c in s.as_bytes() {
            cnt[(c - b'a') as usize] -= 1;
            while mi < 26 && cnt[mi] == 0 {
                mi += 1;
            }
            stk.push(c);
            while let Some(&top) = stk.last() {
                if (top - b'a') as usize <= mi {
                    ans.push(stk.pop().unwrap());
                } else {
                    break;
                }
            }
        }

        String::from_utf8(ans).unwrap()
    }
}

2434. Using a Robot to Print the Lexicographically Smallest String

Description

Solutions

Solution 1: Greedy + Stack

Comments