0234MediumStringStackGreedyMonotonic Stack

Earliest Depot Summary Tag

Tracked in this browser only

Trains the technique from

LeetCode 1081Smallest Subsequence of Distinct Characters

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def summary_tag(route: str) -> str:

Java

public String summaryTag(String route)

The intended approach

Time O(n)Space O(1) beyond the returned tag, since the stack and the final-stop table hold at most one entry per letter

Record the final stop at which each depot is called, then scan the route once while holding the tag built so far on a stack. A depot already on the stack is skipped. Otherwise, while the letter on top of the stack is alphabetically after the current depot and is called at again later, drop it, since it can be re-added from that later stop; then push the current depot.

Pythonentry point: summary_tag

def summary_tag(route):
    last_step = {}
    for step, depot in enumerate(route):
        last_step[depot] = step
    kept = []
    on_tag = set()
    for step, depot in enumerate(route):
        if depot in on_tag:
            continue
        while kept and kept[-1] > depot and last_step[kept[-1]] > step:
            on_tag.discard(kept.pop())
        kept.append(depot)
        on_tag.add(depot)
    return "".join(kept)

The obvious version

Pick the tag letter by letter: compute how far ahead the next pick may sit without stranding an owed depot, then take the alphabetically earliest owed depot inside that reach. O(n^2) with a rescan per pick.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_summary_tag(route):
    # Choose the tag one letter at a time. Everything still owed must appear
    # after the letter picked, which caps how far the pick may reach; inside
    # that reach take the alphabetically earliest owed depot, earliest copy.
    total = len(route)
    chosen = []
    start = 0
    while start < total:
        owed = set(route[start:]) - set(chosen)
        if not owed:
            break
        reach = min(max(j for j in range(start, total) if route[j] == depot)
                    for depot in owed)
        pick = min(route[j] for j in range(start, reach + 1) if route[j] in owed)
        where = min(j for j in range(start, reach + 1) if route[j] == pick)
        chosen.append(pick)
        start = where + 1
    return "".join(chosen)

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in