Show problems as
Classic problem #2434MediumHash TableStringStackGreedy

Using a Robot to Print the Lexicographically Smallest String

Real-world version: Typesetter's Rack
Tracked in this browser only
Read Using a Robot to Print the Lexicographically Smallest String on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A hand typesetter is composing a single line of type. Letter slugs reach the bench on a belt in a fixed order, given as the string slugs. Next to the bench stands a narrow upright rack that holds slugs one above another, and the composed line starts out empty as well.

Each step is one of exactly two moves:

  • take the slug at the head of the belt and set it on top of the rack;
  • take the slug currently on top of the rack and add it to the end of the line.

The typesetter keeps making moves until the belt and the rack are both empty, so every slug ends up somewhere in the line. Many orders of moves are possible and they compose different lines.

Return the composed line that comes first in dictionary order out of all lines the typesetter can produce.

Examples

Example 1

Input
slugs = "tqrq"
Output
"qqrt"

Set `t` and then `q` on the rack, add the top `q` to the line, set `r` and the last `q` on the rack, then add `q`, `r` and `t` to the line in that order. The line reads `qqrt`.

Example 2

Input
slugs = "dgcae"
Output
"acegd"

All five slugs travel from the belt through the rack and into the line, which ends up reading `acegd`.

Example 3

Input
slugs = "mfemf"
Output
"effmm"

Each of the five slugs is added to the line exactly once and the finished line reads `effmm`.

Constraints

  • 1 <= slugs.length <= 10^5
  • slugs consists of lowercase English letters only

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def smallest_printed_line(slugs: str) -> str:
Java
public String smallestPrintedLine(String slugs)

More on the same topics