316. Remove Duplicate Letters

class Solution {
    public String removeDuplicateLetters(String s) {
        // 注意题目要求：使得每个字母只出现一次

        int[] countMap = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            countMap[c - 'a']++;
        }

        StringBuilder sb = new StringBuilder();
        boolean[] exists = new boolean[26];

        // "bcabc"
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (!exists[c - 'a']) { // 不存在才添加该字符
                while (sb.length() > 0 && c < sb.charAt(sb.length() - 1) && countMap[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                    // 出现了下降的字符且之前的字符后续还会再出现，可以安全的删除之前出现的字符
                    char pop = sb.charAt(sb.length() - 1);
                    sb.deleteCharAt(sb.length() - 1);
                    exists[pop - 'a'] = false;
                }

                sb.append(c);
                exists[c - 'a'] = true;
            }

            countMap[c - 'a']--; // 每处理一个字符，维护剩余的字符数
        }

        return sb.toString();
    }
}

References

316. Remove Duplicate Letters
1081. Smallest Subsequence of Distinct Characters