Easy

题目描述

给定一个字符串 s，你有两种类型的操作：

  1. 选择字符串中的一个索引 i，设 c 为位置 i 处的字符。删除 i 左侧最接近的字符 c（如果存在）。
  2. 选择字符串中的一个索引 i，设 c 为位置 i 处的字符。删除 i 右侧最接近的字符 c（如果存在）。

你的任务是通过执行上述操作零次或多次来最小化 s 的长度。

返回一个整数，表示最小化字符串的长度。

示例 1：

输入：s = "aaabc"
输出：3
解释：
- 操作 2：选择 i = 1，c 是 'a'，删除 s[2]，因为它是 s[1] 右侧最接近的 'a' 字符。
  字符串变为 "aabc"。
- 操作 1：选择 i = 1，c 是 'a'，删除 s[0]，因为它是 s[1] 左侧最接近的 'a' 字符。
  字符串变为 "abc"。

示例 2：

输入：s = "cbbd"
输出：3
解释：
- 操作 1：选择 i = 2，c 是 'b'，删除 s[1]，因为它是 s[1] 左侧最接近的 'b' 字符。
  字符串变为 "cbd"。

示例 3：

输入：s = "baadccab"
输出：4

约束条件：

  • 1 <= s.length <= 100
  • s 只包含小写英文字母

提示：

  • 最小化后的字符串不会包含重复字符。
  • 最小化后的字符串将包含原字符串的所有不同字符。

解题思路

解题思路

这道题的关键洞察在于理解操作的本质：无论我们如何选择删除顺序，对于任何重复出现的字符，我们都可以将其减少到只剩一个。

核心观察

  1. 操作的本质：每次操作都是删除某个字符的重复出现
  2. 最终状态：经过足够多的操作后，每个字符最多只会保留一个
  3. 顺序无关性：删除的顺序不影响最终结果

思路分析

由于题目提示告诉我们"最小化后的字符串将包含原字符串的所有不同字符"且"不会包含重复字符"，这意味着最终结果就是原字符串中不同字符的个数。

无论我们选择什么样的删除策略，最终都能将所有重复字符消除，只保留每种字符的一个实例。

解法

最直接的解法就是统计字符串中不同字符的数量：

  • 使用哈希集合存储所有出现过的字符
  • 返回集合的大小

时间复杂度 O(n)，空间复杂度 O(1)（最多26个小写字母）。

代码实现

class Solution {
public:
    int minimizedStringLength(string s) {
        unordered_set<char> unique_chars;
        for (char c : s) {
            unique_chars.insert(c);
        }
        return unique_chars.size();
    }
};

class Solution:
    def minimizedStringLength(self, s: str) -> int:
        return len(set(s))

public class Solution {
    public int MinimizedStringLength(string s) {
        HashSet<char> uniqueChars = new HashSet<char>();
        foreach (char c in s) {
            uniqueChars.Add(c);
        }
        return uniqueChars.Count;
    }
}

var minimizedStringLength = function(s) {
    const uniqueChars = new Set();
    for (const c of s) {
        uniqueChars.add(c);
    }
    return uniqueChars.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)

其中 n 是字符串的长度。空间复杂度为 O(1) 是因为最多只有 26 个不同的小写字母。

相关题目