新手问题 [leetcode] 316 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"
我的解法：
def remove_duplicate_letters(s)
s.chars.sort.uniq.join
end
感觉我没有理解题目的意思。但是我也没看懂题目到底是啥需求？
结果需要能够匹配原题里字母出现的顺序。
Given "cb acd c b c" Return "acdb"
另外请注意一下，这道题的难度是 Medium，不可能只用一句话就做完的。难度是 Super easy 的大概还有可能。
我的解法，用一个 hash 来保存最右侧字符的 index，可以减少判断时间
def remove_duplicate_letters(s)
cs, r = s.chars, []
h = cs.map.with_index.to_h
cs.each_with_index do |c, i|
unless r.include?(c)
r.pop while r.last && c < r.last && i < h[r.last]
r << c
end
end
r.join
end
smallest in lexicographical order 是说需要让去除重复后的字符串最小。这题麻烦的地方也就在这里，需要思考“当有重复的字符的时候，到底该保留哪一个？”。这涉及到如何比较两个字符串的大小，描述起来太麻烦，举几个例子：
"a" == "a"
"a" < "b"
"ab" > "a"
"ab" < "z"
这也是为什么第二个例子的结果会保留第二个 c，而不是第一个。