316. Remove Duplicate Letters

• 전혀 감이 안 와서 못 풀었던 문제. 결국 해답을 봤다.
• Greedy하게 답을 만들어보려고 했는데 규칙을 세우기가 쉽지 않았다.
• 결국 이미 결과 result 에 들어가 있는 것을 상황에 따라 수정하는 방식을 취했어야 했다.

• 문자열을 순회 하면서 결과 result 에 하나씩 넣고 해당 문자를 처리한 것 mark[c] 으로 표시한다.

• 단, 이미 결과 result 에 들어가 있는 문자들 중 현재 문자 s[i] 보다 큰 문자는 결과에서 다시 빼낸다.
• 그래야만 사전식 순서 (lexicographic order)에 따라 가장 작은 문자열을 만들 수 있기 때문이다.
• 단, 빼낼 문자열이 마지막 lastIndex[s[i] - 'a'] 에 해당될 경우 빼지 않고 그대로 둔다.
• 빼낸 문자열은 처리가 안된 것이기 때문에 표시를 다시 원상 복구 시킨다 mark[s[i]] = false .

• 해답에서는 stack을 사용하는 것으로 되어있는데 개념적으로는 꼭 stack이라고 생각할 필요는 없다.
• 본질적으로는 결과 result 에서 현재 문자 보다 큰 것 (단, 마지막인 것은 제외)은 모두 제거하고 현재 문자를 끝에 추가 (append) 하는 것일 뿐이다.
• 다만 결과 result 에서 문자를 뒤에서 부터 제거하는 것이 효율적이라서 stack 처럼 pop하는 방식으로 제거할 뿐이다.

class Solution {
public:
    static constexpr int CHARS = 'z' - 'a' + 1;
    string removeDuplicateLetters(string s) {
        // get last index of each characters
        vector<int> lastIndex(CHARS);
        for (int i = 0; i < s.length(); ++i) {
            lastIndex[s[i] - 'a'] = i;
        }

        vector<char> result;
        vector<bool> mark(CHARS);
        for (int i = 0; i < s.length(); ++i) {
            // skip character if marked
            if (mark[s[i] - 'a']) continue;
            while (!result.empty()) {
                char top = result.back();
                // remove bigger characters from stack
                // except if the character is last one.
                if (top > s[i] && i < lastIndex[top - 'a']) {
                    mark[top - 'a'] = false;
                    result.pop_back();
                } else {
                    break;
                }
            }
            // add current character & mark
            result.push_back(s[i]);
            mark[s[i] - 'a'] = true;
        }

        // convert into string
        return string(result.begin(), result.end());
    }
};