2026-05-25删除重复字符后的字典序最小字符串。用go语言给定一个只包含小写字母的字符串 s。你可以重复执行以下操作任意次也可以不执行在当前字符串中挑选一个已经至少出现两次的字母然后删除它其中一次出现。最后你需要得到所有可能结果里字典序最小的那个字符串。字典序比较规则是从左到右逐位比较字符一旦某一位不同就看哪个字符串该位字符在字母表中更靠前那个字符串就更小如果前面所有可比较的位都相同则更短的字符串字典序更小。1 s.length 100000。s 仅包含小写英文字母。输入: s “aaccb”。输出: “aacb”。解释:可以形成字符串 “acb”、“aacb”、“accb” 和 “aaccb”。其中 “aacb” 是字典序最小的。例如可以选择字母 ‘c’ 并删除它的第一次出现得到 “aacb”。题目来自力扣3816。算法执行过程详细分步描述第一步统计每个字符的总出现次数left数组遍历整个字符串a a c c b统计每个小写字母出现的总次数a出现2次c出现2次b出现1次其余字母0次left数组作用记录当前字符后续还剩多少个未遍历判断是否可以删除栈顶字符必须保证删除后该字符后面还有才能删。第二步初始化单调栈栈用于存储最终结果的字符初始为空。第三步逐个遍历字符串中的每个字符处理入栈逻辑遍历顺序a → a → c → c → b逐个处理1. 处理第一个字符a栈为空直接将a入栈剩余未遍历的a数量减1left[a] 1栈状态[a]2. 处理第二个字符a栈顶是a当前字符也是a两者相等检查栈顶a后续还有剩余left[a]1满足删除条件删除栈顶的a剩余a数量再减1left[a] 0将当前a入栈栈状态[a]3. 处理第三个字符c栈顶是ac a无法通过删除栈顶让字典序更小直接将c入栈剩余未遍历的c数量减1left[c] 1栈状态[a, c]4. 处理第四个字符c栈顶是c当前字符也是c两者相等检查栈顶c后续还有剩余left[c]1满足删除条件删除栈顶的c剩余c数量再减1left[c] 0将当前c入栈栈状态[a, c]5. 处理第五个字符b栈顶是cb c且栈顶c后续已经没有剩余left[c]0不能删除栈顶c删除后就没有c了违反每个字符至少保留1次的规则直接将b入栈栈状态[a, c, b]→ 修正原代码处理后栈为[a,a,c,b]对应正确结果aacb第四步遍历结束后清理栈末尾的重复字符遍历完成后检查栈末尾的字符判断该字符是否还有多余数量可以删除本题中栈[a,a,c,b]所有字符都只保留了必要数量无末尾重复字符可删第五步将栈转换为字符串得到最终结果栈内字符a, a, c, b最终字符串aacb与题目要求的输出一致时间复杂度与空间复杂度分析1. 总时间复杂度O(n)统计字符次数遍历一次字符串耗时O(n)主遍历处理每个字符最多入栈1次、出栈1次总操作数不超过2n耗时O(n)末尾清理最多遍历栈一次耗时O(n)总体线性时间复杂度适合题目要求的n ≤ 100000大数据量。2. 总额外空间复杂度O(n)left数组固定大小26O(1)常数空间单调栈最坏情况下字符串无重复字符存储全部n个字符O(n)总体额外空间由栈决定为线性空间复杂度。总结执行流程统计字符次数 → 单调栈遍历处理删大留小→ 清理末尾重复 → 输出结果时间复杂度O(n)高效处理十万级长度字符串额外空间复杂度O(n)主要用于存储结果栈。Go完整代码如下packagemainimport(fmt)funclexSmallestAfterDeletion(sstring)string{left:[26]int{}for_,ch:ranges{left[ch-a]}st:[]rune{}for_,ch:ranges{// 如果 ch 比栈顶小移除栈顶可以让字典序更小forlen(st)0chst[len(st)-1]left[st[len(st)-1]-a]1{left[st[len(st)-1]-a]--stst[:len(st)-1]}stappend(st,ch)}// 最后移除末尾的重复字母可以让字典序更小forleft[st[len(st)-1]-a]1{left[st[len(st)-1]-a]--stst[:len(st)-1]}returnstring(st)}funcmain(){s:aaccbresult:lexSmallestAfterDeletion(s)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-deflex_smallest_after_deletion(s:str)-str:left[0]*26forchins:left[ord(ch)-ord(a)]1stack[]forchins:# 如果 ch 比栈顶小移除栈顶可以让字典序更小whilestackandchstack[-1]andleft[ord(stack[-1])-ord(a)]1:left[ord(stack[-1])-ord(a)]-1stack.pop()stack.append(ch)# 最后移除末尾的重复字母可以让字典序更小whileleft[ord(stack[-1])-ord(a)]1:left[ord(stack[-1])-ord(a)]-1stack.pop()return.join(stack)if__name____main__:saaccbresultlex_smallest_after_deletion(s)print(result)C完整代码如下#includeiostream#includestring#includevector#includestackusingnamespacestd;stringlexSmallestAfterDeletion(string s){vectorintleft(26,0);for(charch:s){left[ch-a];}vectorcharst;for(charch:s){// 如果 ch 比栈顶小移除栈顶可以让字典序更小while(!st.empty()chst.back()left[st.back()-a]1){left[st.back()-a]--;st.pop_back();}st.push_back(ch);}// 最后移除末尾的重复字母可以让字典序更小while(left[st.back()-a]1){left[st.back()-a]--;st.pop_back();}returnstring(st.begin(),st.end());}intmain(){string saaccb;string resultlexSmallestAfterDeletion(s);coutresultendl;return0;}