README_EN.md

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

Solutions

Python3

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:
    def robotWithString(self, s: str) -> str:
        n = len(s)
        right = [chr(ord('z') + 1)] * (n + 1)
        for i in range(n - 1, -1, -1):
            right[i] = min(s[i], right[i + 1])
        ans = []
        stk = []
        for i, c in enumerate(s):
            stk.append(c)
            while stk and stk[-1] <= right[i + 1]:
                ans.append(stk.pop())
        return ''.join(ans)

Java

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 n = s.length();
        int[] right = new int[n];
        right[n - 1] = n - 1;
        for (int i = n - 2; i >= 0; --i) {
            right[i] = s.charAt(i) < s.charAt(right[i + 1]) ? i : right[i + 1];
        }
        StringBuilder ans = new StringBuilder();
        Deque<Character> stk = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            stk.push(s.charAt(i));
            while (!stk.isEmpty() && (stk.peek() <= (i > n - 2 ? 'z' + 1 : s.charAt(right[i + 1])))) {
                ans.append(stk.pop());
            }
        }
        return ans.toString();
    }
}

C++

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;
    }
};

class Solution {
public:
    string robotWithString(string s) {
        int n = s.size();
        vector<int> right(n, n - 1);
        for (int i = n - 2; i >= 0; --i) {
            right[i] = s[i] < s[right[i + 1]] ? i : right[i + 1];
        }
        string ans;
        string stk;
        for (int i = 0; i < n; ++i) {
            stk += s[i];
            while (!stk.empty() && (stk.back() <= (i > n - 2 ? 'z' + 1 : s[right[i + 1]]))) {
                ans += stk.back();
                stk.pop_back();
            }
        }
        return ans;
    }
};

Go

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)
}

TypeScript

function robotWithString(s: string): string {
    let cnt = new Array(128).fill(0);
    for (let c of s) cnt[c.charCodeAt(0)] += 1;
    let min_index = 'a'.charCodeAt(0);
    let ans = [];
    let stack = [];
    for (let c of s) {
        cnt[c.charCodeAt(0)] -= 1;
        while (min_index <= 'z'.charCodeAt(0) && cnt[min_index] == 0) {
            min_index += 1;
        }
        stack.push(c);
        while (
            stack.length > 0 &&
            stack[stack.length - 1].charCodeAt(0) <= min_index
        ) {
            ans.push(stack.pop());
        }
    }
    return ans.join('');
}

...