题目描述
给你一个字符串 s
。
你需要对 s
执行以下操作 任意 次:
- 选择一个下标
i
,满足s[i]
左边和右边都 至少 有一个字符与它相同。 - 删除
s[i]
左边 离它 最近 且相同的字符。 - 删除
s[i]
右边 离它 最近 且相同的字符。
请你返回执行完所有操作后,s
的 最短 长度。
样例
输入:s = "abaacbcbb"
输出:5
解释:
我们执行以下操作:
选择下标 2,然后删除下标 0 和 3 处的字符,得到 s = "bacbcbb" 。
选择下标 3,然后删除下标 0 和 5 处的字符,得到 s = "acbcb" 。
输入:s = "aa"
输出:2
解释:
无法对字符串进行任何操作,所以返回初始字符串的长度。
限制
1 <= s.length <= 2 * 10^5
s
只包含小写英文字母。
算法
(哈希表,遍历) $O(n + |\Sigma|)$
- 统计每种字符出现的次数。
- 假设某个字符的出现次数为 $t$,则 $t$ 贡献的答案为 $(t-1)/2$ 下取整再乘 $2$。
时间复杂度
- 初始化哈希表时间复杂度为 $O(|\Sigma|)$。
- 遍历字符串,统计字符的出现次数的时间复杂度为 $O(n)$。
- 遍历哈希表累计答案的时间复杂度为 $O(|\Sigma|)$。
- 故总时间复杂度为 $O(n + |\Sigma|)$。
空间复杂度
- 需要 $O(|\Sigma|)$ 的额外空间存储哈希表。
C++ 代码
class Solution {
public:
int minimumLength(string s) {
vector<int> seen(26, 0);
for (char c : s)
++seen[c - 'a'];
int ans = s.size();
for (int i = 0; i < 26; i++)
ans -= (seen[i] - 1) / 2 * 2;
return ans;
}
};