1750. 删除字符串两端相同字符后的最短长度 Medium

给你一个只包含字符 'a'，'b' 和 'c' 的字符串 s ，你可以执行下面这个操作（5 个步骤）任意次：

1. 选择字符串 s 一个 非空 的前缀，这个前缀的所有字符都相同。
2. 选择字符串 s 一个 非空 的后缀，这个后缀的所有字符都相同。
3. 前缀和后缀在字符串中任意位置都不能有交集。
4. 前缀和后缀包含的所有字符都要相同。
5. 同时删除前缀和后缀。

请你返回对字符串 s 执行上面操作任意次以后（可能 0 次），能得到的 最短长度 。

示例 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" 。

解题思路

输入：一个只包含 'a'、'b'、'c' 的字符串 s

输出：在每次移除相同非空前后缀后，返回字符串的最短长度

本题是典型的 相向双指针 问题。

我们可以定义两个指针：left = 0，right = len(s) - 1，从字符串两端向中间遍历。

每当发现 s[left] == s[right]，说明当前可以删除这个字符作为前后缀：

• 向右移动左指针，跳过所有连续等于该字符的前缀；
• 向左移动右指针，跳过所有连续等于该字符的后缀。

重复以上过程，直到 left >= right 或无法再删除。

最终剩余字符串的长度即为 right - left + 1，作为答案返回。

代码实现

python

class Solution:
    def minimumLength(self, s: str) -> int:
        # 定义双指针，分别从字符串两端向中间靠拢
        left, right = 0, len(s) - 1

        # 当左右字符相等时，可以尝试从两边删除相同前缀和后缀
        while left < right and s[left] == s[right]:
            char = s[left]  # 记录当前要删除的字符

            # 向右移动左指针，跳过所有连续的 char
            while left <= right and s[left] == char:
                left += 1

            # 向左移动右指针，跳过所有连续的 char
            while left <= right and s[right] == char:
                right -= 1

        # 剩余字符串长度为 right - left + 1（当 left > right 时返回 0）
        return right - left + 1

javascript

/**
 * @param {string} s
 * @return {number}
 */
const minimumLength = function(s) {
    let left = 0;
    let right = s.length - 1;

    while (left < right && s[left] == s[right]) {
        const char = s[left];

        while (left <= right && s[left] == char) {
            left ++;
        }

        while (left <= right && s[right] == char) {
            right --;
        }
    }

    return right - left + 1;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

1750 国际版

1750 中文版