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

标签: 双指针 字符串

难度: 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" 。

 

提示：

  • 1 <= s.length <= 105
  • s 只包含字符 'a'，'b' 和 'c' 。

Submission

运行时间: 47 ms

内存: 16.2 MB

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 right >= left and s[right] == c:
                right -= 1
        return right - left + 1

Explain

此题解通过使用双指针技术来从两端同时检查字符串。指针left从字符串的起始位置开始，而right从字符串的结束位置开始。目标是在两端找到相同的字符并删除它们。如果当前left和right指向的字符相同，那么这两个字符可以被看作是前缀和后缀。此时，我们向内移动左右两个指针，跳过所有与当前字符相同的字符。这个过程会一直持续到left大于right或者left和right指向的字符不相同为止。最后，返回剩余子字符串的长度，即right - left + 1。

时间复杂度: O(n)

空间复杂度: O(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 right >= left and s[right] == c:  # 移动右指针跳过所有相同字符
                right -= 1
        return right - left + 1  # 返回剩余子字符串的长度

Explore

如果字符串s的左右两端在开始时不相同，则表明这两个字符不需要被删除作为相同的前后缀。在这种情况下，算法直接终止循环，因为没有找到可以删除的相同字符前后缀。最终返回的长度将是整个字符串的长度，即right - left + 1。

如果字符串s的中间存在与两端字符都不相同的一个或多个字符，这些字符不会影响两端相同字符的删除过程。算法主要关注于删除两端相同的字符。一旦两端的字符不相同，中间的字符不会进一步影响处理，因此这些字符将被保留在最终的子字符串中，从而影响最短长度。

这种方法是为了提高算法的效率。由于目标是删除两端相同的字符，如果左右指针指向相同的字符，则可以预设这两端的所有相同字符都是可删除的。因此，一次跳过所有相同的字符而不是逐个比较，可以减少比较的次数，从而减少算法的执行时间。这样做可以直接移动到下一个可能不同的字符，进一步检查是否有新的相同字符可以删除。

在移动left和right指针时，算法通过在while循环条件中检查left <= right来确保left始终小于等于right。这样的条件检查避免了left和right交叉的情况，从而防止了对剩余子字符串长度的错误计算。当left指针超过right指针时，循环终止，这意味着中间没有剩余的字符，或者所有可删除的字符都已被删除。