如何在字典顺序中获得最小的？

Question

我正在做一个leetcode练习

https://leetcode.com/problems/remove-duplicate-letters/

问题是:

# Given a string which contains only lowercase letters, remove duplicate
# letters so that every letter appear once and only once. You must make
# sure your result is the smallest in lexicographical order among all possible results.
#
# Example:
# Given "bcabc"
# Return "abc"
#
# Given "cbacdcbc"
# Return "acdb"

我不太确定what is the smallest in lexicographical order和为什么给予"cbacdcbc"然后答案将是"acdb"

谢谢你的答案提前:)

Answer 1

给定s(s ₁)的第一个字符小于t(t ₁)的第一个字符,或者如果它们是等价的,第二个字符,最小的字典顺序是一个顺序关系,其中字符串s小于t.等等

所以aaabbb小于aaac因为虽然前三个字符相等,但第四个字符b小于第四个字符c.

因为cbacdcbc,有几个选项,因为b并且c是重复的,您可以决定删除哪些重复项.这导致:

cbacdcbc = adbc
cbacdcbc = adcb
cbacdcbc = badc
cbacdcbc = badc
...

因为adbc< adcb,你不能简单地回答你脑海中浮现的第一个答案.

Answer 2

您不能对字符重新排序。如果出现重复字符，您只能选择要删除的事件。

bcabc

我们可以删除 firstb或 second b，我们可以删除 firstc或 second c。总共四个输出：

..abc
.cab.
b.a.c
bca..

按字典顺序（按字母顺序）对这四个输出进行排序：

abc
bac
bca
cab

并采取第一个：

abc