鲁达 2021-08-31：去除重复字母。给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。力扣316。
福大大 答案2021-08-31：
k种字符。
时间复杂度：O(k*N)。
空间复杂度：O(k)。
代码用golang编写。代码如下：
package main import ( "fmt" "strings" ) func main() { str := "abcdea" ret := removeDuplicateLetters1(str) (ret) ret = removeDuplicateLetters2(str) (ret) } // 在str中，每种字符都要保留一个，让最后的结果，字典序最小 ，并返回 func removeDuplicateLetters1(str string) string { if len(str) < 2 { return str } map0 := make([]int, 256) for i := 0; i < len(str); i++ { map0[str[i]]++ } minACSIndex := 0 for i := 0; i < len(str); i++ { if str[minACSIndex] > str[i] { minACSIndex = i } map0[str[i]]-- if map0[str[i]] == 0 { break } } // 0...break(之前) minACSIndex // str[minACSIndex] 剩下的字符串str[minACSIndex+1...] -> 去掉str[minACSIndex]字符 -> s' // s'... return ("%c", str[minACSIndex]) + (str[minACSIndex+1:], ("%c", str[minACSIndex]), "") } func removeDuplicateLetters2(s string) string { // 小写字母ascii码值范围[97~122]，所以用长度为26的数组做次数统计 // 如果map[i] > -1，则代表ascii码值为i的字符的出现次数 // 如果map[i] == -1，则代表ascii码值为i的字符不再考虑 map0 := make([]int, 26) for i := 0; i < len(s); i++ { map0[s[i]-'a']++ } res := make([]byte, 26) index := 0 L := 0 R := 0 for R != len(s) { // 如果当前字符是不再考虑的，直接跳过 // 如果当前字符的出现次数减1之后，后面还能出现，直接跳过 ok := false if !ok { ok = map0[s[R]-'a'] == -1 } if !ok { map0[s[R]-'a']-- ok = map0[s[R]-'a'] > 0 } if ok { R++ } else { // 当前字符需要考虑并且之后不会再出现了 // 在str[L..R]上所有需要考虑的字符中，找到ascii码最小字符的位置 pick := -1 for i := L; i <= R; i++ { if map0[s[i]-'a'] != -1 && (pick == -1 || s[i] < s[pick]) { pick = i } } // 把ascii码最小的字符放到挑选结果中 res[index] = s[pick] index++ // 在上一个的for循环中，str[L..R]范围上每种字符的出现次数都减少了 // 需要把str[pick + 1..R]上每种字符的出现次数加回来 for i := pick + 1; i <= R; i++ { if map0[s[i]-'a'] != -1 { // 只增加以后需要考虑字符的次数 map0[s[i]-'a']++ } } // 选出的ascii码最小的字符，以后不再考虑了 map0[s[pick]-'a'] = -1 // 继续在str[pick + 1......]上重复这个过程 L = pick + 1 R = L } } return string(res[0:index]) }执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class24/Code06_RemoveDuplicateLettersLessLexi.java)