One Bead of Each Color

Medium

Beads are strung on a thread, and each bead's color is a lowercase English letter; the string beads lists them from left to right. A jeweler wants to take beads off so that exactly one bead of every color present remains. Beads cannot be rearranged: the ones left keep their original order. Among all possible results, return the lexicographically smallest string.

Example 1

beads="dbdab" → 'bda'

The colors are a, b and d. Starting with a is impossible, since no d follows the only a. Starting with b (position 1) works, followed by d (position 2) and a, which gives bda.

Example 2

beads="zyxzyx" → 'xzy'

We can start with the first x (position 2), since a z and a y still follow it. That gives xzy.

Example 3

beads="mmm" → 'm'

Constraints

1 ≤ len(beads) ≤ 1000
beads consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Greedy String Monotonic Stack

Similar problems

Every Letter Once Medium Erase Digits for the Smallest Number Medium Smallest Pick With a Required Letter Hard Smallest Up-Down Sequence Medium Fix the Middle of the Line Medium

Input

beads="dbdab"

Expected

'bda'

Run checks the first 3 tests in your browser. Submit checks all 126 tests on the server, hidden ones included.