Remove Duplicate Letters

Question

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.

Solution

這題第一次寫沒寫出來。第一次的想法是，寫個 DFS 去把所有可能的組合都找到，但 DFS 不知道為什麼有錯。

看了解答之後，才發現這是一題需要用遞增棧來想的問題。核心思想在於，先掃一遍矩陣，用 count 記錄每個 char 出現的次數。接著用 stack 來記錄，如果當前的 char 比 stack.peek() 還小 （也就是 stack 不能繼續保持遞增時），檢查 count[cur] 看是否 >0 （也就是代表後面還有該 char），那麼就可以先把前面的刪掉，等後面出現時再加進去。如此就可找出 smallest in lexicographical string

好難RRR~~~

Stack<Character> stack = new Stack<Character>();
    int[] counts = new int[26];
    char[] arr = s.toCharArray();
    for (char c : arr) {
        counts[c - 'a']++;
    }
    boolean[] visited = new boolean[26];
    for (char c : arr) {
        counts[c - 'a']--;
        if (visited[c - 'a']) {
            continue;
        }

        while (!stack.isEmpty() && stack.peek() > c && counts[stack.peek() - 'a'] > 0) {
            visited[stack.peek() - 'a'] = false;
            stack.pop();
        }
        stack.push(c);
        visited[c - 'a'] = true;
    }

    StringBuilder sb = new StringBuilder();
    for (char c : stack) {
        sb.append(c);
    }
    return sb.toString();