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

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]
	}
	return string(t)
}


func main() {
	s:="aabcbbca"
	fmt.Println(lastNonEmptyString(s))
}

Python完整代码如下：

# -*-coding:utf-8-*-

def lastNonEmptyString(s):
    cnt = [0] * 26
    last = [0] * 26

    for i, b in enumerate(s):
        b = ord(b) - ord('a')
        cnt[b] += 1
        last[b] = i

    ids = []
    mx = max(cnt)
    for i, c in enumerate(cnt):
        if c == mx:
            ids.append(last[i])

    ids.sort()

    t = [s[id] for id in ids]
    return ''.join(t)


def main():
    s = "aabcbbca"
    print(lastNonEmptyString(s))


if __name__ == "__main__":
    main()