Leetcode skimming - remove duplicate letters 316 medium

The idea of removing duplicate letters is discussed and the source code
     The title of eliminating repeated letters is shown in the figure below , This question belongs to string type and stack search type , It mainly focuses on the use of string search methods and the understanding of stack structure . The title of this article, the author thought 2 Methods , They are greedy monotone stack method and hash table method , The greedy monotone stack method uses Java Compiling , The hash table method uses Python Compiling , Of course, this may not be the optimal solution , I also hope you guys can give a faster algorithm .

     I think this problem can be solved by greedy monotone stack method , First initialize a length 26 An array of Boolean types of bits and assign values . Then initialize a string list , Start traversing the loop , Take out the character corresponding to the current subscript , Combine it with lowercase letters a Compare , If you haven't traversed , Then search , If the condition is met, the value of boolean type is assigned false Delete this character after , That is, it is considered to be repetition . Then insert the result into the string list , Loop through this logic and return the result until the end . Then according to this idea, our Java The code is as follows ：

# Fire breathing dragon and water arrow turtle 
class Solution {
    public String removeDuplicateLetters(String s) {
        boolean[] numCharArr = new boolean[26];
        int[] num = new int[26];
        for (int ir = 0; ir < s.length(); ir++) {
            num[s.charAt(ir) - 'a']++;
        }

        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (! numCharArr[ch - 'a']) {
                while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) {
                    if (num[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                        numCharArr[sb.charAt(sb.length() - 1) - 'a'] = false;
                        sb.deleteCharAt(sb.length() - 1);
                    } else {
                        break;
                    }
                }
                numCharArr[ch - 'a'] = true;
                sb.append(ch);
            }
            num[ch - 'a'] -= 1;
        }
        return sb.toString();
    }
}

     obviously , We can see that the effect of greedy monotone stack method is ok , At the same time, you can also use the hash table method to solve . First initialize a counter and a queue , The counter can get the number of occurrences of each character , Then start traversing the string , Subtract... From the current number of characters 1, And determine whether the characters are in the list , If so, continue the next cycle , If not, it will iterate through the list , Throw out the elements of the list , Add the current character to the list , Finally, until the end of the loop and return the sum of all elements of the list , That is, the final string . So according to this idea, we can solve , Here is Python Code ：

# Fire breathing dragon and water arrow turtle 
from collections import Counter
class Solution:
    def removeDuplicateLetters(self, s):
        listStack=[]
        sk = Counter(s)
        for jr in s:
            sk[jr] = sk[jr]-1
            if(jr in listStack):
                continue
            while listStack and listStack[-1] > jr and sk[listStack[-1]] > 0:
                    listStack.pop()
            listStack.append(jr)
        return ''.join(listStack)

     As a result Java The efficiency of this version of greedy monotone stack is ok , and Python The speed of the version of hash table method is relatively general , But there should be more ways to further speed up , I hope friends can give me more advice , Thank you very much .