參考英文discuss:
https://leetcode.com/problems/remove-duplicate-letters/discuss/76768/A-short-O(n)-recursive-greedy-solution

這個leetcode discuss上的答案對于我個人而言非常難以理解,而且這哥們寫的解釋過于抽象,在鉆研了一番之后,寫出了自己對這個問題的理解,希望給讀者朋友們一個參考

原題描述:

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: "bcabc"
Output: "abc"
Example 2:

Input: "cbacdcbc"
Output: "acdb"

在解決這個問題之前先要明白兩件事,不明白沒法做,

1. 結(jié)果不能改變原字符串中字符的相對順序.
2. 結(jié)果是最小字典序(希望詳細(xì)了解的可以自己去查一下),比如abcd這四個字母最小字典序就是abcd,第二是abdc,要輸出的結(jié)果就是這四個字母的最小排列(字典序),并且不能改變原字符串的相對順序.

詳細(xì)解釋見代碼注釋

        public String removeDuplicateLetters(String s) {
            final int n = s.length();
            if (n == 0) {
                return "";
            }
            int[] cnt = new int[26];
            int pos = 0;
            // 這里不做詳細(xì)解釋,楞看都看得懂
            for (int i = 0; i < n; ++i) {
                ++cnt[s.charAt(i) - 'a'];
            }
            for (int i = 0; i < n; ++i) {
                // 找相對字典序最小的字符,定位為pos
                if (s.charAt(i) < s.charAt(pos)) {
                    pos = i;
                }
                // 1. 在[i...m]已經(jīng)沒有對應(yīng)的字符s[i]了,在這里結(jié)束循環(huán)
                // 2. 因為此時會選擇字典序最小的字符,這個字符是pos,s[pos](相對字典序最小的字符,且pos <= i,s[pos]<=s[i])
                // Note : 這里才是最關(guān)鍵的,根據(jù)貪心的原理, 原集合S中選出一個最優(yōu)子集A,得到的子集S-A總是存在最優(yōu)選擇,最優(yōu)解與貪心選擇組合即可得到原問題的最優(yōu)解.
                if (--cnt[s.charAt(i) - 'a'] == 0) {
                    break;
                }
            }

            // 3. 此時去掉所有在字符串中出現(xiàn)的s[pos],并將s[pos]加到當(dāng)前遞歸過程中生成的子字符串的第一個字符.
            // 4. 繼續(xù)遞歸子字符串.
            return s.charAt(pos) +
                    removeDuplicateLetters(s.substring(pos + 1).replaceAll("" + s.charAt(pos), ""));
        }