What is the main trick in Minimize String Length?

The key is using a hash set or fixed array to track unique letters, since the minimized string length equals the number of distinct characters.

Can this approach handle strings up to length 100 efficiently?

Yes, iterating once with a set or array provides O(n) time complexity, easily handling strings of length up to 100.

Do I need to preserve the original order of characters?

No, only the count of unique letters matters. Order is irrelevant for minimized length.

Is using a hash table always better than sorting?

Yes, because sorting adds O(n log n) overhead while a hash set counts unique letters in O(n).

Does this solution apply to other string minimization problems?

Yes, any problem where duplicates are removed to minimize length can use the Hash Table plus String pattern efficiently.

#2716

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

最小化字符串长度

给你一个下标从 0 开始的字符串 s ，重复执行下述操作任意次：在字符串中选出一个下标 i ，并使 c 为字符串下标 i 处的字符。并在 i 左侧（如果有）和右侧（如果有）各删除一个距离 i 最近的字符 c 。请你通过执行上述操作任意次，使 s 的长度最小化。返回一个表示 …

哈希表字符串

题目描述

给你一个下标从 0 开始的字符串 s ，重复执行下述操作任意次：

在字符串中选出一个下标 i ，并使 c 为字符串下标 i 处的字符。并在 i 左侧（如果有）和右侧（如果有）各删除一个距离 i 最近的字符 c 。

请你通过执行上述操作任意次，使 s 的长度 最小化 。

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

示例 1：

输入：s = "aaabc"
输出：3
解释：在这个示例中，s 等于 "aaabc" 。我们可以选择位于下标 1 处的字符 'a' 开始。接着删除下标 1 左侧最近的那个 'a'（位于下标 0）以及下标 1 右侧最近的那个 'a'（位于下标 2）。执行操作后，字符串变为 "abc" 。继续对字符串执行任何操作都不会改变其长度。因此，最小化字符串的长度是 3 。

示例 2：

输入：s = "cbbd"
输出：3
解释：我们可以选择位于下标 1 处的字符 'b' 开始。下标 1 左侧不存在字符 'b' ，但右侧存在一个字符 'b'（位于下标 2），所以会删除位于下标 2 的字符 'b' 。执行操作后，字符串变为 "cbd" 。继续对字符串执行任何操作都不会改变其长度。因此，最小化字符串的长度是 3 。

示例 3：

输入：s = "dddaaa"
输出：2
解释：我们可以选择位于下标 1 处的字符 'd' 开始。接着删除下标 1 左侧最近的那个 'd'（位于下标 0）以及下标 1 右侧最近的那个 'd'（位于下标 2）。执行操作后，字符串变为 "daaa" 。继续对新字符串执行操作，可以选择位于下标 2 的字符 'a' 。接着删除下标 2 左侧最近的那个 'a'（位于下标 1）以及下标 2 右侧最近的那个 'a'（位于下标 3）。执行操作后，字符串变为 "da" 。继续对字符串执行任何操作都不会改变其长度。因此，最小化字符串的长度是 2 。

提示：

1 <= s.length <= 100
s 仅由小写英文字母组成

lightbulb

解题思路

方法一：哈希表

题目实际上可以转化为求字符串中不同字符的个数，因此，我们只需要统计字符串中不同字符的个数即可。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串 $\textit{s}$ 的长度。空间复杂度 $O(|\Sigma|)$ ，其中 $\Sigma$ 是字符集，这里是小写英文字母，因此 $|\Sigma|=26$ 。

1

2

3

4

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

speed

复杂度分析

指标	值
时间	complexity is O(n) since each character is processed once. Space complexity is O(1) with a fixed 26-letter array or O(k) for a hash set storing k unique letters.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on identifying unique characters efficiently.
question_mark
Expect a simple hash table or set-based solution for string reduction.
question_mark
Watch for off-by-one errors when counting duplicates.

warning

常见陷阱

外企场景

error
Trying to remove duplicates manually with nested loops, leading to O(n^2) time.
error
Forgetting that only the count of unique characters matters, not their order.
error
Using extra memory unnecessarily instead of a fixed-size array or set.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Minimize string length for uppercase letters using a similar hash table approach.
arrow_right_alt
Return the minimized string itself instead of just the length.
arrow_right_alt
Count unique characters after allowing limited repeated removals or restricted operations.

help

常见问题

外企场景

继续练习

#2707 字符串中的额外字符 #2744 最大字符串配对数目 #2767 将字符串分割为最少的美丽子字符串