关于OA回顾
这个系列旨在记录参加过的一些日本互联网公司的OA原题。考虑到私密性等问题，文中只会记录题目的内容而不会指明该题来自于哪一家公司。
题目概述
现有一个由英文小写字母构成的字符串s。对其进行去重操作（在字符串中出现的每一种字母只保留一个，不改变原有的顺序），返回操作完成后得到的字符串中字典序最大的那一个。
限制条件：
1 <= s.length <= 10 ^ 5
例:
1
2
3
4
5
Input: s = abacaba
Output: cba
Input: s = aazb
Output: azb
思路 & 代码实现
对于一个字符串来说，越靠前的字母对字典序的影响越大。如果希望整个字符串的字典序尽可能大，我们首先需要考虑的就是设法让该字符串的第一个字母尽可能大，然后再依次考虑后续的字母大小。具体的思路大概是这样：
- 遍历字符串
- 创建一个栈用于保存遍历中的每个时刻下所能获得的无重复字母的最大字典序字符串
- 若遍历到的字母已经在栈中，则跳过
- 若遍历到的字母大于栈顶字母，并且栈顶字母在后续的字符串中还会出现，则将栈顶字母弹出
- 重复上述操作直到栈顶字母不满足出栈或栈为空时，将遍历到的字母入栈
注意这一条：
并且栈顶字母在后续的字符串中还会出现
为了确认特定字母是否还会在后续的字符串中出现，我们还需要额外创建一个哈希表，表中存储在原字符串中出现过的每一种字母于字符串中最后一次出现的位置。
至此，我们便可以通过维护这样的一个栈以贪心地存储每个状态下的最大字典序字符串，并在遍历完成后得到基于整个字符串的最优解了。具体的代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import defaultdict
def solution(s):
last_index = {c: i for i, c in enumerate(s)}
stk = []
for i, c in enumerate(s):
if c in stk:
continue
while stk and stk[-1] < c and i < last_index[stk[-1]]:
stk.pop()
stk.append(c)
return "".join(stk)
Time complexity: $O(n)$
Space complexity: $O(1)$
