Show problems as
Classic problem #1081MediumStringStackGreedyMonotonic Stack

Smallest Subsequence of Distinct Characters

Real-world version: Earliest Depot Summary Tag
Tracked in this browser only
Read Smallest Subsequence of Distinct Characters on LeetCode(opens in a new tab)

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

A courier's shift is logged as route, a string of lowercase letters where the letter at each position is the depot called at that stop. A depot can be called at any number of times.

Dispatch files the shift under a summary tag, which is built by dropping stops from route. A tag is valid when it names every depot the shift called at, each of them once and only once, and the letters it keeps appear in the same order they were called in.

Several valid tags usually exist. Return the one that comes first in alphabetical order. Every valid tag has the same length, namely the number of distinct depots in route, so comparing two tags never runs off the end of one of them.

Examples

Example 1

Input
route = "dacbdc"
Output
"abdc"

The shift called at depots a, b, c and d. Dropping the stops at positions 0, 2 and 4 leaves a, b, d, c, which names each of those depots once and keeps them in the order they were called.

Example 2

Input
route = "bca"
Output
"bca"

Each of b, c and a is called at once, so the only valid tag keeps every stop.

Example 3

Input
route = "mmmm"
Output
"m"

Only depot m is ever called at, so the tag names it a single time.

Constraints

  • 1 <= route.length <= 1000
  • route consists of lowercase English letters

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 summary_tag(route: str) -> str:
Java
public String summaryTag(String route)

More on the same topics