Medium

题目描述

给你一个字符串 s。

你可以对 s 执行以下操作任意次数：

  • 选择字符串中的一个索引 i，使得在索引 i 的左侧至少有一个字符等于 s[i]，在右侧也至少有一个字符等于 s[i]。
  • 删除位于 i 左侧最近的 s[i] 字符。
  • 删除位于 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 仅由小写英文字母组成。

解题思路

这道题的关键洞察是：只有字符的出现频次重要，而不是字符的具体位置。

根据题目描述，我们可以删除一个字符当且仅当它的左右两侧都至少有一个相同字符。这意味着：

  • 如果一个字符出现次数少于3次，我们无法对它执行删除操作
  • 如果一个字符出现次数≥3次，我们可以重复删除两个字符，直到剩余次数≤2

核心思想：

  1. 统计每个字符的出现频次
  2. 对于每个字符：
    • 如果频次≤2，所有字符都保留
    • 如果频次>2，我们可以通过操作将其减少到1或2个
    • 具体来说，如果频次为奇数，最终剩余1个；如果为偶数，最终剩余2个

为什么是这样？ 每次操作删除2个相同字符，所以奇数频次的字符最终剩余1个，偶数频次的字符最终剩余0个。但题目要求左右都有相同字符才能删除，所以至少要保留1个。因此偶数频次的字符最终剩余2个。

等等，让我重新分析：每次操作实际上是删除3个字符中的2个（选中间的，删除左右的），所以频次为n的字符，最终剩余n%2==1时剩1个，n%2==0时剩2个。

代码实现

class Solution {
public:
    int minimumLength(string s) {
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }
        
        int result = 0;
        for (auto& [ch, count] : freq) {
            if (count <= 2) {
                result += count;
            } else {
                result += (count % 2 == 1) ? 1 : 2;
            }
        }
        
        return result;
    }
};

class Solution:
    def minimumLength(self, s: str) -> int:
        from collections import Counter
        
        freq = Counter(s)
        result = 0
        
        for count in freq.values():
            if count <= 2:
                result += count
            else:
                result += 1 if count % 2 == 1 else 2
        
        return result

public class Solution {
    public int MinimumLength(string s) {
        Dictionary<char, int> freq = new Dictionary<char, int>();
        
        foreach (char c in s) {
            freq[c] = freq.GetValueOrDefault(c, 0) + 1;
        }
        
        int result = 0;
        foreach (int count in freq.Values) {
            if (count <= 2) {
                result += count;
            } else {
                result += (count % 2 == 1) ? 1 : 2;
            }
        }
        
        return result;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var minimumLength = function(s) {
    const freq = {};
    for (let char of s) {
        freq[char] = (freq[char] || 0) + 1;
    }
    
    let result = 0;
    for (let count of Object.values(freq)) {
        if (count % 2 === 0) {
            result += 2;
        } else {
            result += 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历字符串一次统计频次，然后遍历频次表
空间复杂度O(1)最多存储26个小写字母的频次，常数空间