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

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {string} s
 * @return {string}
 */
const robotWithString = function (s) {
  const BASE_CODE = 'a'.charCodeAt(0);
  const counts = Array.from({ length: 26 }, () => 0);
  const stack = [];
  const result = [];
  let smallestCode = 0;

  const getCode = letter => letter.charCodeAt(0) - BASE_CODE;

  for (const letter of s) {
    const code = getCode(letter);

    counts[code] += 1;
  }

  for (const letter of s) {
    const code = getCode(letter);

    counts[code] -= 1;
    stack.push(letter);

    while (smallestCode < 26 && !counts[smallestCode]) {
      smallestCode += 1;
    }

    while (stack.length && getCode(stack.at(-1)) <= smallestCode) {
      const current = stack.pop();

      result.push(current);
    }
  }

  return result.join('');
};