2024-07-20：用go语言，给定一个字符串 s， 依次遍历 ‘a‘ 到 ‘z‘， 每次操作删除 s 中出现位置最早的字符，

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完整代码如下：

在这里插入图片描述Python完整代码如下：

# -*-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()

在这里插入图片描述