题目描述
思路解析动画文字版
记牢:两个指针 i、j 盯两端。s[i] 和 s[j] 相同才删,把左右各自一整段相同字符都跳完再内移;两端不同或指针交叉就停。答案是 max(0, j-i+1)。下面每帧都在套它。
总览 · 目标是把两端一层层剥掉：先看清画面。上面这排格子是 s 等于 aabccabba,下标 0 到 8,一共 9 个字符。我们要不停地把「字符相同的一头一尾」一起删掉,让它越缩越短。右边面板记三件事:左指针 i 在哪、右指针 j 在哪、现在剩多长,一开始都还没摆好。
开局 · 双指针分别站在两端：摆好两个指针:i 站在最左边下标 0,j 站在最右边下标 8。接下来的套路很简单,每一层都先看这两端的字符是不是同一个,是就一起剥掉,不是就收工。先看这一层。
第 1 层 · 两端都是 a：先比两端。左指针 i 在下标 0,字符是 a;右指针 j 在下标 8,字符也是 a。两端同字符,这一层可以删。绿色把这一对先标出来。接下来要把左边一连串 a、右边一连串 a 都跳干净。
第 1 层左段 · 从下标 0 起的 a：先看左边这段相同字符。从下标 0 的 a 起步,绿色标住它。只要右邻还是同一个 a,左段就能往右延伸。看下标 1。
第 1 层左段 · 延伸到下标 1：下标 1 还是 a,和左边的 a 一样,左段往右长一格,现在是两个 a,盖住下标 0 和 1。i 也跟着挪到下标 1。再看下一个。
第 1 层左段 · 遇 b 停：下标 2 是 b,不是 a 了,标红提醒。左边这段相同字符到下标 1 就结束,一共两个 a。左段跳完,换右边看。
第 1 层右段 · 从下标 8 起的 a：再看右边这段相同字符,用蓝色标。从下标 8 的 a 起步。只要它的左邻还是 a,右段就能往左延伸。看下标 7。
第 1 层右段 · 遇 b 停：下标 7 是 b,不是 a,标红。右边这段相同字符就只有下标 8 一个 a。注意了:左边有两个 a、右边只有一个 a,个数不一样没关系,字符都是 a 就一起删。
第 1 层 · 两端的 a 一起删：动手删。左边两个 a、右边一个 a 一起拿掉,灰掉的下标 0、1、8 就是删除的部分。这一层删了 3 个字符,还剩 6 个。
第 1 层收尾 · 指针内移到 2 和 7：删完两端,指针各往里挪:i 到下标 2,j 到下标 7。现在有效的字符串是 bccabb,下标 2 到 7。右边面板剩余长度更新成 6。进入下一层。
第 2 层 · 两端都是 b：再比两端。左指针 i 在下标 2 是 b,右指针 j 在下标 7 也是 b,两端同字符,这一层继续删。绿色标住这一对。照旧,把左右各自的相同字符段跳完。
第 2 层左段 · 只有一个 b：看左段。下标 2 是 b,右邻下标 3 是 c,标红,已经不同了。所以左边这段相同字符只有下标 2 一个 b。左段跳完,看右边。
第 2 层右段 · 从下标 7 起的 b：看右段,蓝色标。从下标 7 的 b 起步。只要它左邻还是 b,右段就能往左延伸。看下标 6。
第 2 层右段 · 延伸到下标 6：下标 6 也是 b,和右边的 b 一样,右段往左长一格,盖住下标 6 和 7 两个 b。j 也跟着挪到下标 6。再往左看一个。
第 2 层右段 · 遇 a 停：下标 5 是 a,不是 b 了,标红。右边这段相同字符到下标 6 结束,一共两个 b。这回反过来:左边一个 b、右边两个 b,照样一起删。
第 2 层 · 两端的 b 一起删：动手删。左边一个 b、右边两个 b 一起拿掉,灰掉下标 2、6、7。这一层又删了 3 个,现在只剩 3 个字符了。
第 2 层收尾 · 指针内移到 3 和 5：删完两端,指针再往里挪:i 到下标 3,j 到下标 5。现在有效的字符串是 cca,下标 3 到 5。剩余长度更新成 3。看看还能不能删。
第 3 层 · 两端 c 与 a 不同,停：再比两端。左指针 i 在下标 3 是 c,右指针 j 在下标 5 是 a,一个 c 一个 a,不是同一个字符,标红。规则说前缀后缀字符必须相同才能删,这里删不了,循环到此为止。
揭晓 · 剩下 cca 共 3 个：把剩下的摆出来。下标 3 到 5 是 c、c、a 三个字符,两端 c 和 a 不同,再也删不动了。长度就是右指针减左指针加 1,也就是 5 减 3 加 1 等于 3。
回放 · 两层各从两端剥掉相同字符：回放一下整个过程。第 1 层两端都是 a,左边删掉两个 a、右边删掉一个 a;第 2 层两端都是 b,左边删掉一个 b、右边删掉两个 b。两层一共删了 6 个字符,原来 9 个减去 6 个,正好剩下中间的 cca 这 3 个。
完成 · 最短长度 = 3：收个尾。我们用两个指针从两端往中间夹,每层只要两端字符相同,就把左右各自一整段相同字符都删掉再内移;一旦两端不同或指针交叉就停。s 等于 aabccabba 一路删下来,最短长度是 3。整个过程指针只往里走,线性时间、常数空间。
边界:两端不同返回原长(ca 得 2);能删空返回 0(靠 max 兜底);单字符 i 不小于 j 循环不进、返回 1。
面试重点:两端同字符时整段删掉是安全贪心、不漏优解;前后缀各自独立挑、相同字符个数可不等;i 只右移、j 只左移各不回头,故 O(n) 时间、O(1) 空间。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def minimumLength(self, s: str) -> int: i, j = 0, len(s) - 1 while i < j and s[i] == s[j]: while i + 1 < j and s[i] == s[i + 1]: i += 1 while i < j - 1 and s[j - 1] == s[j]: j -= 1 i, j = i + 1, j - 1 return max(0, j - i + 1)复杂度
- 时间：O(n)，n 是字符串长度。左指针 i 只会往右走、右指针 j 只会往左走,两个指针合起来最多把整个字符串扫一遍,内层跳相同字符段也是它们各自的前进,不会回头。所以总的比较次数是线性的,和 n 成正比
- 空间：O(1)，按峰值算。除了输入字符串本身,只用了 i、j 两个下标和一个返回值,都是常数个变量,不随字符串变长而增加,也没有额外开数组或新建字符串,所以额外空间是常数级
易错点
面试追问把动画讲成自己的话
追问为什么可以贪心地把两端整段相同字符都删掉,不会漏掉更优解?
追问左右两段相同字符的个数为什么可以不一样?
追问这个双指针为什么是 O(n) 时间、O(1) 空间?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
邻位交换的最小次数
LeetCode 1850 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题