[LeetCode] 316. Remove Duplicate Letters

轉自LeetCode

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

 

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

 

Constraints:

• 1 <= s.length <= 104
• s consists of lowercase English letters.

Solution

這題比較難的地方是，最後的答案中的字母順序，前後的相對關係必須保持一樣

例如 exmple2 的答案是 "acdb" 而不是 "abcd"

想法是用一個 map 來記錄每個 char 出現的次數，以及一個 set 來看有沒有用過

如果當下的 char 有用過，直接忽略

如果沒用過，但是比目前 ans 最後一個字母小，且 map 裡的值大於零(代表後面還會出現)

就把 ans 最後一個字母移除

kotlin