LeetCode 题解工作台
进行操作使字符串为空
给你一个字符串 s 。 请你进行以下操作直到 s 为 空 ： 每次操作 依次 遍历 'a' 到 'z' ，如果当前字符出现在 s 中，那么删除出现位置 最早 的该字符（如果存在的话）。 例如，最初 s = "aabcbbca" 。我们执行下述操作： 移除下划线的字符 s = " a a bc bbc…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用一个哈希表或数组 记录字符串 中每个字符的出现次数，用一个哈希表或数组 记录字符串 中每个字符最后一次出现的位置。字符串 中出现次数最多的字符的出现次数记为 。 然后我们遍历字符串 ，如果当前字符的出现次数等于 且当前字符所在位置等于该字符最后一次出现的位置，那么我们将当前字符加入答案中。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个字符串 s 。
请你进行以下操作直到 s 为 空 ：
- 每次操作 依次 遍历
'a'到'z'，如果当前字符出现在s中，那么删除出现位置 最早 的该字符（如果存在的话）。
例如，最初 s = "aabcbbca"。我们执行下述操作：
- 移除下划线的字符
s = "aabcbbca"。结果字符串为s = "abbca"。 - 移除下划线的字符
s = "abbca"。结果字符串为s = "ba"。 - 移除下划线的字符
s = "ba"。结果字符串为s = ""。
请你返回进行 最后 一次操作 之前 的字符串 s 。在上面的例子中，答案是 "ba"。
示例 1：
输入：s = "aabcbbca" 输出："ba" 解释：已经在题目描述中解释。
示例 2：
输入：s = "abcd" 输出："abcd" 解释：我们进行以下操作： - 删除 s = "abcd" 中加粗加斜字符，得到字符串 s = "" 。 进行最后一次操作之前的字符串为 "abcd" 。
提示：
1 <= s.length <= 5 * 105s只包含小写英文字母。
解题思路
方法一：哈希表或数组
我们用一个哈希表或数组 记录字符串 中每个字符的出现次数，用一个哈希表或数组 记录字符串 中每个字符最后一次出现的位置。字符串 中出现次数最多的字符的出现次数记为 。
然后我们遍历字符串 ，如果当前字符的出现次数等于 且当前字符所在位置等于该字符最后一次出现的位置，那么我们将当前字符加入答案中。
遍历结束后，返回答案即可。
时间复杂度 ，空间复杂度 ，其中 是字符串 的长度，而 是字符集，本题中 为小写英文字母。
class Solution:
def lastNonEmptyString(self, s: str) -> str:
cnt = Counter(s)
mx = cnt.most_common(1)[0][1]
last = {c: i for i, c in enumerate(s)}
return "".join(c for i, c in enumerate(s) if cnt[c] == mx and last[c] == i)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of operations and frequency updates, roughly O(n) if each character is scanned once. Space complexity is O(1) for character counts plus O(n) for the output string storage. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Tracking character counts efficiently hints at using a hash table.
- question_mark
Maintaining the correct order while removing characters is key for correct output.
- question_mark
Optimizing repeated scans of the string can be done with array marking or stack-based approaches.
常见陷阱
外企场景- error
Failing to update character counts after each operation can lead to incorrect results.
- error
Rescanning the entire string unnecessarily increases time complexity.
- error
Ignoring the order of remaining characters can produce a wrong final string.
进阶变体
外企场景- arrow_right_alt
Allowing removal operations based on custom character priority instead of frequency.
- arrow_right_alt
Restricting operations to contiguous substrings rather than individual characters.
- arrow_right_alt
Tracking multiple strings simultaneously and applying operations in parallel.