leetcode 316 解题报告

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

算起来可能有将近两三年没有刷过题了。OI 或者 ACM 什么的和真正做点什么的乐趣比起来还是差一些。不过最近为了准备之后的面试，想要稍微熟悉一下常用的算法，所以选择做一些 Leetcode 上的题目。同样，刷题不是目的，重要的是回忆从题目中抽象出算法的过程。所以有了这篇以及以后的一些解题报告。

题目描述

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”

分析

题目要求去掉所有重复的字母，并且使得最后的结果字典序最小。初看没有什么明显的算法，甚至连明显易行的暴力策略都没想出。于是从结果入手。要求只能去掉某些字母，意味着不能改变原字符串字母的顺序，并且结果中包含了出现的所有字母。从这里可以想到，把最终结果串中的前缀子串放回原字符串中时，其后面一定出现了其它所有当前未选出的字母。这个应该是解题的关键。拿第二个样例来说明：

原字符串中出现的所有字母是 abcd，所以最终结果中 a 的后面一定出现了 bcd，ac 的后面一定出现了 bd，acd 的后面一定出现了 b。

因此，假设我们已经选出了一些字母作为结果字符串，在决定下一个字符的时候，只要看它是否满足当前未选出的字母在它之后全部出现这个条件。另一个很明显可以想到的问题是会有多个字母满足这个条件，那根据题目，我们只要取那个字典序最小的出来就可以了。

归纳起来，我们的算法可以这样表述：

1. 选出其后出现了所有未选出的字母的字母。
2. 从中选出字典序最小的那个。

先来解决第一个问题，我们如何知道当前字母后是否出现了其他所有字母呢？先用最朴素的想法，遍历它后面的字母，统计是否每一个字母都出现了。这个想法最大的问题是，我们做了大量的重复工作，后面的字母被重复统计了很多次。优化的思路也很明显，倒着统计。在具体实现时，我们并不需要知道具体哪个字母出现了，因为我们已经知道了需要的字母的总数，所以只要统计不重复的字母个数就好了。一个 bool 数组和一个计数器可以搞定。

在做上述统计的过程中，计数器的值是递增的。当它递增到未选出字母的总数的时候，我们知道此时前面所有的字母就都是满足要求的字母了。接下来从中选出最小的字母取出，并且把该字母从剩余序列中去掉即可。

另外很明显的一点限制就是，选出的字母一定要满足原序列中的顺序。所以当从原序列中选出一个字母以后，它左边的字母就不能再被选择了。这个限制引出的问题是，当上一步最小的字母出现不止一次的时候，我们该选择哪一个？

这也是我第一次 Wrong answer 的原因，考虑这个例子：

babcacb

第一次扫描统计的时候，从右边第一个 a 开始，计数器的值就已经为 3 了，此时满足条件的最小字母是 a。而如果选择了右边的 a，那么得出的结果是 acb，如果是左边的 a，结果是 abc。也就是说，我们要选择让剩余子串长度更长的那个字母，因为在这两者之间可能出现了最优解。

最后总结一下算法：

1. 在给定字符串中从后往前统计出现未重复字母个数，记为 m
2. 从 m 等于当前未选出字母个数的字母中选出最小并且位置最靠左的字母 x
3. 把 x 以及 x 左边的字符去掉
4. 从剩余字符串中把 x 去掉
5. 重复 1-5，直到剩余字符串为空