2024-07-20：用go语言，给定一个字符串 s，
依次遍历 'a' 到 'z'，
每次操作删除 s 中出现位置最早的字符，
直到 s 为空为止。
返回最后一次操作前的字符串 s。
举例来说，以s = "aabcbbca"为例，根据上述操作规则：
第一轮操作后，s = "aabcbbca"，删除最早出现的 'a'、'b'、'c'，得 s = "abbca"。
第二轮操作后，s = "abbca"，删除最早出现的 'a'、'b'、'c'，得 s = "ba"。
第三轮操作后，s = "ba"，删除最早出现的 'a'、'b'，得 s = ""。
因此最后一次操作前的字符串是"ba"。
答案2024-07-20：
chatgpt
题目来自leetcode3039。
大体步骤如下：
1.遍历字符串s，统计每个字母出现的次数以及最后一次出现的位置，并存储在cnt和last两个数组中。这个过程的时间复杂度为O(n)，其中n为字符串s的长度，额外空间复杂度为O(1)。
2.找出出现次数最多的字母，记录其最后一次出现的位置。这个过程需要遍历26个小写字母，时间复杂度为O(26)≈O(1)，额外空间复杂度为O(1)。
3.找到所有出现次数最多的字母对应的最后一次出现的位置，存储在ids数组中。这个过程的时间复杂度也是O(n)，额外空间复杂度为O(n)。
4.对ids数组进行排序，时间复杂度为O(nlogn)，额外空间复杂度为O(1)。
5.根据ids数组中的位置信息，构造出最后一次操作前的字符串t。这个过程的时间复杂度为O(n)，额外空间复杂度为O(n)。
综上所述，总的时间复杂度为O(nlogn)，总的额外空间复杂度为O(n)。
Go完整代码如下：
代码语言：javascript复制package main
import(
"fmt"
"slices"
)
func lastNonEmptyString(s string)string{
var cnt,last[26]int
for i, b :=range s {
b -='a'
cnt[b]
last[b]= i
}
// 注：也可以再遍历一次 s 直接得到答案，但效率不如下面，毕竟至多 26 个数
ids :=[]int{}
mx := slices.Max(cnt[:])
for i, c :=range cnt {
if c == mx {
ids =append(ids,last[i])
}
}
slices.Sort(ids)
t :=make([]byte,len(ids))
for i, id :=range ids {
t[i]= s[id]
}
returnstring(t)
}
func main(){
s:="aabcbbca"
fmt.Println(lastNonEmptyString(s))
}
Python完整代码如下：
代码语言：javascript复制# -*-coding:utf-8-*-
deflastNonEmptyString(s):
cnt =[0]*26
last =[0]*26
for i, b inenumerate(s):
b =ord(b)-ord('a')
cnt[b] =1
last[b]= i
ids =[]
mx =max(cnt)
for i, c inenumerate(cnt):
if c == mx:
ids.append(last[i])
ids.sort()
t =[s[id]foridin ids]
return''.join(t)
defmain():
s ="aabcbbca"
print(lastNonEmptyString(s))
if __name__ =="__main__":
main()
