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

🎯 问题描述（来源于LeetCode）

描述：
给你一个只包含字符 'a'、'b' 和 'c' 的字符串 s，你可以执行以下操作任意次：

  • 选择字符串的一个非空前缀和一个非空后缀，要求前缀和后缀的所有字符都相同，且前缀和后缀的字符相同（即 s[0] == s[-1]）。然后删除前缀和后缀，剩余部分拼接成新字符串。
    求在执行任意次操作后，字符串可能的最短长度。

说明：

  • 每次操作必须同时删除前缀和后缀，且前缀和后缀的字符必须相同。
  • 如果两端字符不同，则无法继续操作，返回当前长度。

示例：

  • 示例 1：
1
2
3
输入: s = "ca"
输出: 2
解释: 两端字符 'c' 和 'a' 不同，无法删除，长度为 2。
  • 示例 2：
1
2
3
4
5
6
输入: s = "cabaabac"
输出: 0
解释: 
  初始: "cabaabac" 两端都为 'c'，删除所有 'c' 得到 "abaaba"。
  现在两端为 'a' 和 'a'，删除所有 'a' 得到 "b"。
  但注意：删除前缀和后缀时要求它们连续相同，实际上 "abaaba" 两端为 'a'，删除所有连续 'a' 后，中间 "b" 长度为1，但最后两端 'b' 不同，结果应为1？实际上标准答案是0？需要核对。根据LeetCode示例，输入 "cabaabac" 输出 0，因为删除两端相同字符块后最终为空。
  • 示例 3：
1
2
输入: s = "aabccabba"
输出: 3

💻 解题思路

思路：双指针删除相同字符块

算法步骤

  1. 初始化左指针 left = 0，右指针 right = len(s) - 1。
  2. 当 left < right 且 s[left] == s[right] 时：
    • 记录当前字符 ch = s[left]。
    • 从左边删除所有与 ch 相同的连续字符：while left <= right and s[left] == ch: left += 1。
    • 从右边删除所有与 ch 相同的连续字符：while left <= right and s[right] == ch: right -= 1。
  3. 循环结束后，若 left > right，说明全部删除，返回 0；否则返回 right - left + 1。

代码实现（您的代码）

1
2
3
4
5
6
7
8
9
10
class Solution:
    def minimumLength(self, s: str) -> int:
        left, right = 0, len(s) - 1
        while left < right and s[left] == s[right]:
            ch = s[left]
            while left <= right and s[left] == ch:
                left += 1
            while left <= right and s[right] == ch:
                right -= 1
        return right - left + 1 if left <= right else 0

📊 性能分析

  • 时间复杂度：O(n)O(n)，每个字符最多被访问一次。
  • 空间复杂度：O(1)O(1)，仅使用常数个变量。

思考

您的代码正确实现了题意：每次从两端删除所有与当前相同字符的连续块，并继续检查新的两端。注意内层两个 while 循环分别删除左右两侧的相同字符块，确保删除的是前缀和后缀中所有连续的该字符。最终若指针交错则返回 0，否则返回剩余长度。该解法是本题的标准双指针解法，高效且简洁。