class Solution {
public:
string lastNonEmptyString(string s) {
}
};
3039. 进行操作使字符串为空
给你一个字符串 s 。
请你进行以下操作直到 s 为 空 ：
'a' 到 'z'，如果当前字符出现在 s 中，那么删除出现位置 最早 的该字符。请你返回进行 最后 一次操作 之前 的字符串 s 。
示例 1：
输入：s = "aabcbbca" 输出："ba" 解释：我们进行以下操作： - 删除 s = "aabcbbca" 中加粗加斜字符，得到字符串 s = "abbca" 。 - 删除 s = "abbca" 中加粗加斜字符，得到字符串 s = "ba" 。 - 删除 s = "ba" 中加粗加斜字符，得到字符串 s = "" 。 进行最后一次操作之前的字符串为 "ba" 。
示例 2：
输入：s = "abcd" 输出："abcd" 解释：我们进行以下操作： - 删除 s = "abcd" 中加粗加斜字符，得到字符串 s = "" 。 进行最后一次操作之前的字符串为 "abcd" 。
提示：
1 <= s.length <= 5 * 105s 只包含小写英文字母。原站题解
golang 解法, 执行用时: 31 ms, 内存消耗: 7 MB, 提交时间: 2024-02-19 10:36:20
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)
}
python3 解法, 执行用时: 354 ms, 内存消耗: 19.1 MB, 提交时间: 2024-02-19 10:36:00
class Solution:
def lastNonEmptyString(self, s: str) -> str:
last = {c: i for i, c in enumerate(s)} # 每个字母最后出现的位置
cnt = Counter(s) # 每个字母出现的频率
mx = max(cnt.values()) # 出现次数最多的次数
ids = sorted(last[ch] for ch, c in cnt.items() if c == mx) # 取出现最多次数的字母，按最后出现的位置排序
return ''.join(s[i] for i in ids)