# 1081. Smallest Subsequence of Distinct Characters
###### tags: `Leetcode` `Medium` `Stack`
Link: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
## 思路
和[0316. Remove Duplicate Letters](https://hackmd.io/Sob4u8GMTTu0o8Myn0ue7w)
这道题的思路应该是先想怎么维护一个字符递增的子串，然后再想怎么保证字母不重复且每个字母都会出现一次
- 维护递增子串
用单调栈，每次发现栈顶元素比现在元素大，就一直pop到栈顶元素比现在元素小或相同
- 保证字母不重复
就需要记录哪些字符在栈里面，已经存在的不再放进去了
- 每个字母都出现一次
如果这个字符应该被pop，但是发现后面不再有这个字符了，就要留下来，并且不再继续pop

## Code

class Solution {
    public String smallestSubsequence(String s) {
        int[] freq = new int[26];
        boolean[] visited = new boolean[26];
        
        for(int i = 0;i < s.length();i++){
            freq[s.charAt(i)-'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < s.length();i++){
            char ch = s.charAt(i);
            if(!visited[ch-'a']){
                while(sb.length()>0 && sb.charAt(sb.length()-1)>ch){
                    if(freq[sb.charAt(sb.length()-1)-'a']!=0){
                        visited[sb.charAt(sb.length()-1)-'a'] = false;
                        sb.deleteCharAt(sb.length()-1);
                    }
                    else{
                        break;
                    }
                }
                visited[ch-'a'] = true;
                sb.append(ch);
            }
            freq[ch-'a']--;
        }
        return sb.toString();
    }
}