Medium

题目描述

给你一个仅由字符 ‘a’、‘b’ 和 ‘c’ 组成的字符串 s。你需要对字符串执行以下算法任意次数（可能是零次）：

  • 从字符串 s 中选择一个非空前缀，该前缀中的所有字符都相等。
  • 从字符串 s 中选择一个非空后缀，该后缀中的所有字符都相等。
  • 前缀和后缀在任何索引处都不能相交。
  • 前缀和后缀中的字符必须相同。
  • 删除前缀和后缀。

返回执行上述操作任意次数后 s 的最小长度。

示例 1：

输入：s = "ca"
输出：2
解释：你无法删除任何字符，所以字符串保持不变。

示例 2：

输入：s = "cabaabac"
输出：0
解释：最优的操作序列是：
- 选择前缀 = "c" 和后缀 = "c" 并删除它们，s = "abaaba"。
- 选择前缀 = "a" 和后缀 = "a" 并删除它们，s = "baab"。
- 选择前缀 = "b" 和后缀 = "b" 并删除它们，s = "aa"。
- 选择前缀 = "a" 和后缀 = "a" 并删除它们，s = ""。

示例 3：

输入：s = "aabccabba"
输出：3
解释：最优的操作序列是：
- 选择前缀 = "aa" 和后缀 = "a" 并删除它们，s = "bccabb"。
- 选择前缀 = "b" 和后缀 = "bb" 并删除它们，s = "cca"。

约束条件：

  • 1 <= s.length <= 10^5
  • s 仅由字符 ‘a’、‘b’ 和 ‘c’ 组成。

解题思路

这道题的核心思想是使用双指针从字符串两端同时收缩，寻找可以删除的相同字符前缀和后缀。

解题思路：

  1. 双指针策略：使用左右两个指针分别从字符串的开始和结束位置出发。
  2. 匹配条件：只有当左右指针指向的字符相同时，才能执行删除操作。
  3. 贪心删除：每次操作都尽可能多地删除相同的字符，即从左边删除所有连续的相同字符，从右边删除所有连续的相同字符。
  4. 终止条件：当左右指针相遇或交叉时，或者两端字符不相同时，停止操作。

算法流程：

  • 初始化左指针 left = 0，右指针 right = s.length - 1
  • 当 left < right 且 s[left] == s[right] 时：
    • 记录当前字符 c = s[left]
    • 移动左指针直到遇到不同字符或越界
    • 移动右指针直到遇到不同字符或越界
  • 返回剩余字符串长度 max(0, right - left + 1)

这种贪心策略是最优的，因为每次操作都最大化了删除的字符数量。

代码实现

class Solution {
public:
    int minimumLength(string s) {
        int left = 0, right = s.length() - 1;
        
        while (left < right && s[left] == s[right]) {
            char c = s[left];
            while (left <= right && s[left] == c) {
                left++;
            }
            while (left <= right && s[right] == c) {
                right--;
            }
        }
        
        return right - left + 1;
    }
};

class Solution:
    def minimumLength(self, s: str) -> int:
        left, right = 0, len(s) - 1
        
        while left < right and s[left] == s[right]:
            c = s[left]
            while left <= right and s[left] == c:
                left += 1
            while left <= right and s[right] == c:
                right -= 1
        
        return right - left + 1

public class Solution {
    public int MinimumLength(string s) {
        int left = 0, right = s.Length - 1;
        
        while (left < right && s[left] == s[right]) {
            char c = s[left];
            while (left <= right && s[left] == c) {
                left++;
            }
            while (left <= right && s[right] == c) {
                right--;
            }
        }
        
        return right - left + 1;
    }
}

var minimumLength = function(s) {
    let left = 0, right = s.length - 1;
    
    while (left < right && s[left]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个字符最多被访问两次（左指针一次，右指针一次）
空间复杂度O(1)只使用了常数个额外变量