3223.md

title	description	keywords
3223. 操作后字符串的最短长度	LeetCode 3223. 操作后字符串的最短长度题解，Minimum Length of String After Operations，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 3223. 操作后字符串的最短长度 操作后字符串的最短长度 Minimum Length of String After Operations 解题思路 哈希表 字符串 计数

3223. 操作后字符串的最短长度

🟠 Medium  🔖  哈希表 字符串 计数  🔗 力扣 LeetCode

题目

You are given a string s.

You can perform the following process on s any number of times:

• Choose an index i in the string such that there is at least one character to the left of index i that is equal to s[i], and at least one character to the right that is also equal to s[i].
• Delete the closest character to the left of index i that is equal to s[i].
• Delete the closest character to the right of index i that is equal to s[i].

Return the minimum length of the final string s that you can achieve.

Example 1:

Input: s = "abaacbcbb"

Output: 5

Explanation:
We do the following operations:

• Choose index 2, then remove the characters at indices 0 and 3. The resulting string is s = "bacbcbb".
• Choose index 3, then remove the characters at indices 0 and 5. The resulting string is s = "acbcb".

Example 2:

Input: s = "aa"

Output: 2

Explanation:
We cannot perform any operations, so we return the length of the original string.

Constraints:

• 1 <= s.length <= 2 * 10^5
• s consists only of lowercase English letters.

题目大意

给你一个字符串 s 。

你需要对 s 执行以下操作 任意 次：

• 选择一个下标 i ，满足 s[i] 左边和右边都 至少 有一个字符与它相同。
• 删除 s[i] 左边 离它 最近 且相同的字符。
• 删除 s[i] 右边 离它 最近 且相同的字符。

请你返回执行完所有操作后， s 的 最短 长度。

示例 1：

输入： s = "abaacbcbb"

输出： 5

解释：
我们执行以下操作：

• 选择下标 2 ，然后删除下标 0 和 3 处的字符，得到 s = "bacbcbb" 。
• 选择下标 3 ，然后删除下标 0 和 5 处的字符，得到 s = "acbcb" 。

示例 2：

输入： s = "aa"

输出： 2

解释：
无法对字符串进行任何操作，所以返回初始字符串的长度。

提示：

• 1 <= s.length <= 2 * 10^5
• s 只包含小写英文字母。

解题思路

1. 初始化

   • 初始化变量 res 为字符串的长度 s.length。

2. 字符计数

   • 使用长度为 26 的数组 count，每个索引代表一个字母的计数。
   • 小写字母的 ASCII 范围是 'a' 到 'z'，对应的值是 97 到 122。
   • 我们可以通过计算 char.charCodeAt() - 97 将每个字母映射到数组索引 0 到 25。
   • 遍历字符串时，增加对应字母的计数。
   • 当某个字符的计数达到 3 时，重置计数为 1（相当于移除 2 个字符），并将结果长度 res 减少 2。

3. 最终结果

   • 遍历结束后，返回 res，即移除所有出现三次的字符后，字符串的最短长度。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度，遍历字符串一次。
• 空间复杂度：O(1)，使用一个长度为 26 的数组。

代码

/**
 * @param {string} s
 * @return {number}
 */
var minimumLength = function (s) {
	let res = s.length;
	let count = new Array(26).fill(0);
	for (let char of s) {
		const index = char.charCodeAt() - 97; // 计算字母在数组中的索引
		count[index]++;
		if (count[index] == 3) {
			count[index] = 1;
			res -= 2;
		}
	}
	return res;
};