LeetCode——最小化字符串长度

╰+攻爆jí腚メ 2023-10-12 10:17 31阅读 0赞

**目录**

一、题目

二、题目解读

三、代码

1、set去重

2、用一个二进制数记录每个字母是否出现过

--------------------

## 一、题目 ##

[6462. 最小化字符串长度 - 力扣（Leetcode）][6462. _ - _Leetcode]

给你一个下标从 **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` 仅由小写英文字母组成

## 二、题目解读 ##

> 根据题目我们可以 删除 与下标为i的字符c 左右最近的相同字符c，且可以进行这个操作 **任意** 次。所以可以得出：最后每个不同的字符都只会保留一个。
> 
> 读懂了题目之后，这题就特别简单了。

## 三、代码 ##

#### 1、set去重 ####

class Solution {
        public int minimizedStringLength(String s) {
            HashSet<Character> set=new HashSet<>();
            for (int i=0;i<s.length();i++){
                set.add(s.charAt(i));
            }
            return set.size();
        }
    }

#### 2、用一个二进制数记录每个字母是否出现过 ####

[数位 DP【力扣周赛 348】\_哔哩哔哩\_bilibili][DP_ 348_bilibili]

我也是看了 灵茶山艾府 大佬的题解。

class Solution {
        public int minimizedStringLength(String s) {
            int mask = 0;
            for (int c : s.toCharArray())
                mask |= 1 << (c - 'a');
            return Integer.bitCount(mask);
        }
    }

![94117a053e584b2db739d5ecf7253801.png][]

![3c6fc276acdd465e90d0f11f2fd40691.gif][]

[6462. _ - _Leetcode]: https://leetcode.cn/problems/minimize-string-length/description/
[DP_ 348_bilibili]: https://www.bilibili.com/video/BV1do4y1K7Wq/?spm_id_from=333.337.search-card.all.click&vd_source=04372dd1994830c9ba33498f2e4e408c
[94117a053e584b2db739d5ecf7253801.png]: https://img-blog.csdnimg.cn/94117a053e584b2db739d5ecf7253801.png
[3c6fc276acdd465e90d0f11f2fd40691.gif]: https://img-blog.csdnimg.cn/3c6fc276acdd465e90d0f11f2fd40691.gif