每日一题-力扣-2716: 最小化字符串长度 0328-EW帮帮网

LeetCode 2716: 最小化字符串长度问题剖析

在这里插入图片描述

题目解读

LeetCode 2716 是一道关于字符串操作的算法题。这道题乍看复杂，实则蕴含着优雅的数学规律。题目要求通过一系列特定的删除操作来最小化字符串的长度：

给定一个下标从 0 开始的字符串 s
每次操作可以选择字符串中的一个下标 i，并使用 i 处的字符 c 作为参考
删除 c 左侧（如果存在）和右侧（如果存在）各一个与 c 相同且距离最近的字符
重复操作直到无法继续删除
返回字符串可能达到的最小长度

深入思考

作者在分析这道题时，首先观察了给出的三个示例，并试图找出其中的规律。经过仔细推敲，发现：在任何情况下，最终的字符串中每种字符最多只会出现一次。

为什么会这样？通过以下推理：

假设字符串中存在多个相同的字符，例如 “aabcaa”，其中有多个 ‘a’。我们可以选择中间的一个 ‘a’（例如第二个 ‘a’），然后删除其左右两侧最近的 ‘a’，这样就能消除三个 ‘a’ 中的两个。通过类似的操作，我们可以确保任何字符最多只保留一个。

这一发现极大地简化了问题：答案就是字符串中不同字符的数量。

实现方案

方法一：集合去重（最优解）

使用集合（Set）是解决此问题的最优方法。集合天然具有去重的特性，完美契合本题需求：

class Solution:
    def minimizedStringLength(self, s: str) -> int:
        # 利用集合去重特性，直接返回不同字符的数量
        return len(set(s))

这个解法简洁优雅，复杂的操作序列最终归结为简单的集合基数计算。

方法二：哈希表计数

对于更习惯使用哈希表的读者，另一种思路：

class Solution:
    def minimizedStringLength(self, s: str) -> int:
        char_dict = {}
        for char in s:
            char_dict[char] = True  # 值不重要，只关心键的存在
        return len(char_dict)

这种方法本质上与集合方法相同，但表达方式略有不同，可能更适合一些习惯面向对象思维的开发者。

方法三：Counter 类实现

对于 Python 爱好者，推荐使用 collections 模块的 Counter 类：

from collections import Counter

class Solution:
    def minimizedStringLength(self, s: str) -> int:
        # Counter 会自动统计每个字符的出现次数
        char_counter = Counter(s)
        # 我们只关心有多少种不同的字符
        return len(char_counter)

Counter 类提供了一种更加 Pythonic 的解决方案，尤其在需要进一步处理字符频率的场景中更为有用。

方法四：位运算（针对小写字母）

针对特定条件下的优化，还提出了一种位运算方案：

class Solution:
    def minimizedStringLength(self, s: str) -> int:
        # 假设字符串只包含小写字母
        mask = 0
        for char in s:
            # 将对应字母的位置置为1
            mask |= (1 << (ord(char) - ord('a')))
        
        # 计算二进制中1的个数，即不同字符的数量
        return bin(mask).count('1')

这种位运算方法在字符集有限（如本题中的小写英文字母）时尤为高效，因为它利用了整数的二进制表示，将空间复杂度降至 O(1)。

算法分析

对各方法进行了深入分析：

时间复杂度：所有方法都需要遍历字符串一次，时间复杂度为 O(n)，其中 n 是字符串长度。值得注意的是，方法四在某些编程语言中可能有更优的常数因子，特别是在字符集较小时。
空间复杂度：
- 方法一、二、三：O(min(n, C))，其中 C 是字符集大小。在最坏情况下（所有字符都不同），空间复杂度为 O(n)；在最好情况下（字符集有限，如小写字母），空间复杂度为 O©。
- 方法四：O(1)，因为使用固定大小的整数存储位掩码。
代码简洁度：方法一（集合）最为简洁，反映了问题的本质。

案例分析与验证

为了加深理解，进一步分析了几个具体案例：

示例 “aaabc”：
- 可以选择中间的 ‘a’，删除两侧的 ‘a’，得到 “abc”
- 不同字符有 3 个：‘a’, ‘b’, ‘c’
- 最小长度为 3，与集合大小一致
示例 “abbbcd”：
- 可以选择中间的 ‘b’，删除两侧的 ‘b’，得到 “abcd”
- 不同字符有 4 个：‘a’, ‘b’, ‘c’, ‘d’
- 最小长度为 4，与集合大小一致
边缘情况 “a”：
- 只有一个字符，无法进行操作
- 不同字符有 1 个：‘a’
- 最小长度为 1，与集合大小一致

通过这些案例，验证了理论的正确性。

拓展思考

思考问题的几个变种：

如果规则改为"只删除左侧"或"只删除右侧"，问题会变得更加复杂，可能需要动态规划来解决。
如果允许选择不同的字符作为锚点，而不是必须选择相同的字符，那么问题的性质会完全改变。
如果要求返回操作的最小次数，而不是最终长度，则需要计算每种字符的出现次数减一的总和。

总结

LeetCode 2716 是一道典型的"看似复杂实则简单"的问题，它教会我们在复杂操作背后寻找数学规律的重要性。最终解法之所以如此优雅，是因为我们发现了问题的本质 - 不管如何操作，最终每种字符最多只能保留一个。

这种"化繁为简"的思维方式，是解决算法问题的一大法宝。正如本题所示，有时候最优解并不在于设计复杂的算法，而在于深刻理解问题本身。

每日一题-力扣-2716: 最小化字符串长度 0328