进行操作使字符串为空

标签: 数组 哈希表 计数 排序

难度: Medium

给你一个字符串 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 * 105
  • s 只包含小写英文字母。

Submission

运行时间: 134 ms

内存: 18.6 MB

class Solution:
    def lastNonEmptyString(self, s: str) -> str:
        cnt = Counter(s)
        last = {c: i for i, c in enumerate(s)}
        mn = max(cnt.values())
        ids = sorted(last[ch] for ch, c in cnt.items() if c == mn)
        return ''.join(s[i] for i in ids)

Explain

这个题解似乎并不完全符合题目的要求。题目要求移除字符串中按字母表顺序出现的最早字符，直到字符串为空。但题解中的方法更像是查找并返回出现最多次的字符的最后出现位置的字符串。具体步骤如下： 1. 使用Counter计算每个字符在字符串中出现的次数。 2. 构建一个字典记录每个字符最后一次出现的位置。 3. 找到出现次数最多的字符，记录这些字符最后一次出现的索引。 4. 按索引顺序返回这些字符组成的字符串。

时间复杂度: O(n + k log k)

空间复杂度: O(1)

from collections import Counter

class Solution:
    def lastNonEmptyString(self, s: str) -> str:
        # 计数每个字符的出现次数
        cnt = Counter(s)
        # 记录每个字符最后一次出现的位置
        last = {c: i for i, c in enumerate(s)}
        # 找到出现次数最多的字符
        mn = max(cnt.values())
        # 获取这些最常出现字符的最后位置，并排序
        ids = sorted(last[ch] for ch, c in cnt.items() if c == mn)
        # 根据索引构建并返回结果字符串
        return ''.join(s[i] for i in ids)

Explore

题解中的算法确实与题目要求不符。这可能是因为题解的作者误解了题目的要求或者是题解错误地被应用到了这个问题上。正确的做法应该是按照题目要求，迭代地遍历字母表，依次移除字符串中第一次出现的字符，直到字符串为空。题解中的方法更适合用于统计字符出现频率并按特定规则输出字符，这与原题的目标有本质的不同。

`Counter`是一个非常高效的工具，用于统计数据中元素的出现频率。它的时间复杂度通常为O(n)，其中n是字符串的长度。对于大型数据集，这通常是可接受的。然而，如果我们知道字符集是有限的（例如ASCII字符），则可以使用固定大小的数组或字典来手动计数，这可能在某些情况下稍微提高效率。但总体来说，`Counter`已足够优化，适用于大多数情况。

这个排序操作的时间复杂度是O(k log k)，其中k是出现次数最多的字符数量。在最坏的情况下，如果每个字符的出现次数都相同，k可以达到字符集的大小，可能接近或等于n。通常，排序操作可能会在性能上有所影响，特别是当k接近n时。然而，这是否有重大影响取决于具体情况，包括数据的大小和分布。如果k相对较小，则这种影响可能不大。