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

🟠   🔖  哈希表 字符串 计数  🔗 力扣 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;
};