LeetCode_ Monotonic stack_ Medium_ 316. Remove duplicate letters

1. subject

Give you a string s , Please remove the duplicate letters from the string , Make each letter appear only once . Ensure that the dictionary order of the returned results is the smallest （ The relative position of other characters should not be disturbed ）.

Example 1：
Input ：s = “bcabc”
Output ：“abc”

Example 2：
Input ：s = “cbacdcbc”
Output ：“acdb”

Tips ：
1 <= s.length <= 10⁴
s It's made up of lowercase letters

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/remove-duplicate-letters

2. Ideas

（1） Monotonic stack

3. Code implementation （Java）

// Ideas 1———— Monotonic stack 
class Solution {
    
    public String removeDuplicateLetters(String s) {
    
        int length = s.length();
        Stack<Character> stack = new Stack<>();
        /* cnt[0] Record string  s  In the character  a  Number of occurrences of  cnt[1] Record string  s  In the character  b  Number of occurrences of  ......  And so on  */
        int[] cnt = new int[26];
        for (int i = 0; i < length; i++) {
    
            cnt[s.charAt(i) - 'a']++;
        }
        // boolean  The initial value of the elements in the array defaults to  false
        boolean[] inStack = new boolean[26];
        for (char c : s.toCharArray()) {
    
            // Every time you traverse a character , Reduce the corresponding times by one 
            cnt[c - 'a']--;
            if (inStack[c - 'a']) {
    
                continue;
            }
            while (!stack.isEmpty() && stack.peek() > c) {
    
                // If there is no stack top element after , Then stop  pop
                if (cnt[stack.peek() - 'a'] == 0) {
    
                    break;
                }
                // If there are elements after , Then you can  pop
                inStack[stack.pop() - 'a'] = false;
            }
            stack.push(c);
            inStack[c - 'a'] = true;
        }
    
        StringBuilder builder = new StringBuilder();
        while (!stack.isEmpty()) {
    
            builder.append(stack.pop());
        }
        return builder.reverse().toString();
    }
}