Remove duplicate letters （ The smallest sequence of different characters ） problem

author ：Grey

Original address ： Remove duplicate letters （ The smallest sequence of different characters ） problem

Title Description

LeetCode 316. Remove Duplicate Letters

LeetCode 1081. Smallest Subsequence of Distinct Characters

Ideas

Because the title says , Strings are all lowercase letters , So step one ,

We can set one containing 26 An array of elements to count the frequency of each character

        char[] str = s.toCharArray();
        int[] map = new int[26];
        for (char c : str) {
    
            map[c - 'a']++;
        }

By the above method , You can get the word frequency of each character ,

The second step , We set two pointers

int l = 0;
int r = 0;

Move first r The pointer ,r Move one position at a time , Just reduce the word frequency of the characters in this position by one , If r Some time comes i Location ,i The word frequency of the character in the position is reduced by one, and then it disappears , This means that from [l...r] The interval can find a minimum ASCII The characters of begin to settle , hypothesis [l...r] Minimum ASCII The characters are in p Location , Then we need to do the following ：

First step ： take p The character of position is added to the result string .

The second step ： take p The word frequency of the position is set to -1, Easy to identify p The character of position has been used , You can skip it next time ：map[str[p]-'a']=-1

The third step ： take [p+1...r] The word frequency of characters is increased again 1, Because this part of the characters is reduced .

Step four ：r and l All come to p+1 Location , Continue the above process .

The example is as follows ：

The original string and word frequency table are as follows ：

Next r The word frequency of the position character is reduced by one ,r To the next position

At this time, no word frequency will be reduced to 0, Keep moving r,

Next move r, notes ： here d The word frequency of is about to be reduced to 0,

Next , Start collecting the first element , That is to say [l...r] Within the interval , find ASCII The smallest element , namely 2 Position no. a Elements , here , take a Collected into the result string , And record a Position at this time , namely p=2.

then , We need to put the whole string a The word frequency of is set to -1, Express a Characters have been collected , namely
map['a'-'a']=-1.

Last , because a Location is the collected location , and r Has traversed to 3 Position no. d Elements , So from a Location to r All elements in the position , You have to increase the word frequency again （ Because every time you move r Will delete word frequency ）.

The complete code is as follows ：

    public static String removeDuplicateLetters(String s) {
    
        char[] str = s.toCharArray();
        int[] map = new int[26];
        for (char c : str) {
    
            map[c - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        int l = 0;
        int r = 0;
        while (r < str.length) {
    
            if (map[str[r] - 'a'] == -1 || --map[str[r] - 'a'] > 0) {
    
                // r In a processed location or r After the word frequency on is subtracted, it does not arrive 0, Explain now 
                //  It's not the time to count 
                // r don 't worry ++
                r++;
            } else {
    
                // r The word frequency of position has been reduced to 0 了 
                //  It's ready to settle 
                int p = l;
                for (int i = l; i <= r; i++) {
    
                    if (map[str[i] - 'a'] != -1 && str[i] < str[p]) {
    
                        p = i;
                    }
                }
                if (map[str[p] - 'a'] != -1) {
    
                    //  The settlement location must be a valid location 
                    sb.append(str[p]);
                    //  After settlement , Set the word frequency of this position to -1, It is convenient to judge whether this position has been used in the future 
                    map[str[p] - 'a'] = -1;
                }
                for (int i = p + 1; i <= r; i++) {
    
                    // [p+1,r] Between the position of the characters , Restore the word frequency , Because this part of the word frequency is reduced 
                    if (map[str[i] - 'a'] != -1) {
    
                        map[str[i] - 'a']++;
                    }
                }
                l = p + 1;
                r = l;
            }
        }
        return sb.toString();
    }

more

Algorithm and data structure notes