###### tags: `LeetCode` `Duplicate`

# 0316. Remove Duplicate Letters (Medium)
耗時：>60 分鐘 (看別人解答)

## 題目
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.

## 思路
1. 一開始考慮以循序判斷的方式解析字串，或是以substring的方式divide and conquer，但始終有考慮上的死角，雖然有想到unique(僅有一個的字母，不能被刪除)，但沒有成功解題。

2. 別人解答的思路總結：在unique前的最小字母就是該子字串的解！
以pos為當前字母，循序找出較小的字母，並重新以他為字串起始點
若找到unique，則遞迴判斷子字串

舉例來說：cbacdacbc, d為unique，因此我們可以分解為S1:(~~cb~~a)，S2:(cdacbc)，S1中的a為最小字母，且於unique前，則a為S1的唯一解(**不會有比a小的字母無法被刪除**)

* Time Complexity：O(n)
* Space Complexity：O(n^2)
* Worst Case：全部字母皆為unique, space= n + (n-1) + (n-2) + ... + 1 = O(n^2)

### 程式碼
參考別人的解答：

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int cnt[26] = {0};
        int pos = 0;
        for (int i = 0; i < s.length(); ++i) cnt[s[i] - 'a']++;
        for (int i = 0; i < s.length(); ++i) {
            // find smaller head
            if (s[i] < s[pos])
                pos = i;
            // find unique number
            if (--cnt[s[i] - 'a'] == 0)
                break;
        }
        if (s.length() - pos > 0) {
            string sub = s.substr(pos+1);
            string sub_2 = "";
            for (int i = 0; i < sub.length(); ++i)
                if (sub[i] == s[pos])
                    sub[i] = '_';
                else
                    sub_2.push_back(sub[i]);
            return  s[pos] + removeDuplicateLetters(sub_2);
        }
        else
            return "";
    }
};