Question

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

Solution 1: Greedy + Stack

The problem can be transformed into, given a string sequence, convert it into the lexicographically smallest string sequence with the help of an auxiliary stack.

We can use an array cnt to maintain the occurrence count of each character in string $s$, use a stack stk as the auxiliary stack in the problem, and use a variable mi to maintain the smallest character in the string that has not been traversed yet.

Traverse the string $s$, for each character $c$, we first decrement the occurrence count of character $c$ in array cnt, and update mi. Then push character $c$ into the stack. At this point, if the top element of the stack is less than or equal to mi, then loop to pop the top element of the stack, and add the popped character to the answer.

After the traversal ends, return the answer.

The time complexity is $O(n+C)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string $s$, and $C$ is the size of the character set, in this problem $C=26$.

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 {
  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('');
}

Solution 2

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)

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

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