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

这道题到底在问什么

输入

s="ca"

输出

2

输入

s="cabaabac"

输出

0

输入

s="aabccabba"

输出

3

最优解：一步一步想明白

1. 3记牢:两个指针 i、j 盯两端。s[i] 和 s[j] 相同才删,把左右各自一整段相同字符都跳完再内移;两端不同或指针交叉就停。答案是 max(0, j-i+1)。下面每帧都在套它。
2. 4先看清画面。上面这排格子是 s 等于 aabccabba,下标 0 到 8,一共 9 个字符。我们要不停地把「字符相同的一头一尾」一起删掉,让它越缩越短。右边面板记三件事:左指针 i 在哪、右指针 j 在哪、现在剩多长,一开始都还没摆好。
3. 5摆好两个指针:i 站在最左边下标 0,j 站在最右边下标 8。接下来的套路很简单,每一层都先看这两端的字符是不是同一个,是就一起剥掉,不是就收工。先看这一层。
4. 6先比两端。左指针 i 在下标 0,字符是 a;右指针 j 在下标 8,字符也是 a。两端同字符,这一层可以删。绿色把这一对先标出来。接下来要把左边一连串 a、右边一连串 a 都跳干净。
5. 7先看左边这段相同字符。从下标 0 的 a 起步,绿色标住它。只要右邻还是同一个 a,左段就能往右延伸。看下标 1。
6. 8下标 1 还是 a,和左边的 a 一样,左段往右长一格,现在是两个 a,盖住下标 0 和 1。i 也跟着挪到下标 1。再看下一个。
7. 9下标 2 是 b,不是 a 了,标红提醒。左边这段相同字符到下标 1 就结束,一共两个 a。左段跳完,换右边看。
8. 10再看右边这段相同字符,用蓝色标。从下标 8 的 a 起步。只要它的左邻还是 a,右段就能往左延伸。看下标 7。
9. 11下标 7 是 b,不是 a,标红。右边这段相同字符就只有下标 8 一个 a。注意了:左边有两个 a、右边只有一个 a,个数不一样没关系,字符都是 a 就一起删。
10. 12动手删。左边两个 a、右边一个 a 一起拿掉,灰掉的下标 0、1、8 就是删除的部分。这一层删了 3 个字符,还剩 6 个。
11. 13删完两端,指针各往里挪:i 到下标 2,j 到下标 7。现在有效的字符串是 bccabb,下标 2 到 7。右边面板剩余长度更新成 6。进入下一层。
12. 14再比两端。左指针 i 在下标 2 是 b,右指针 j 在下标 7 也是 b,两端同字符,这一层继续删。绿色标住这一对。照旧,把左右各自的相同字符段跳完。
13. 15看左段。下标 2 是 b,右邻下标 3 是 c,标红,已经不同了。所以左边这段相同字符只有下标 2 一个 b。左段跳完,看右边。
14. 16看右段,蓝色标。从下标 7 的 b 起步。只要它左邻还是 b,右段就能往左延伸。看下标 6。
15. 17下标 6 也是 b,和右边的 b 一样,右段往左长一格,盖住下标 6 和 7 两个 b。j 也跟着挪到下标 6。再往左看一个。
16. 18下标 5 是 a,不是 b 了,标红。右边这段相同字符到下标 6 结束,一共两个 b。这回反过来:左边一个 b、右边两个 b,照样一起删。
17. 19动手删。左边一个 b、右边两个 b 一起拿掉,灰掉下标 2、6、7。这一层又删了 3 个,现在只剩 3 个字符了。
18. 20删完两端,指针再往里挪:i 到下标 3,j 到下标 5。现在有效的字符串是 cca,下标 3 到 5。剩余长度更新成 3。看看还能不能删。
19. 21再比两端。左指针 i 在下标 3 是 c,右指针 j 在下标 5 是 a,一个 c 一个 a,不是同一个字符,标红。规则说前缀后缀字符必须相同才能删,这里删不了,循环到此为止。
20. 22把剩下的摆出来。下标 3 到 5 是 c、c、a 三个字符,两端 c 和 a 不同,再也删不动了。长度就是右指针减左指针加 1,也就是 5 减 3 加 1 等于 3。
21. 23回放一下整个过程。第 1 层两端都是 a,左边删掉两个 a、右边删掉一个 a;第 2 层两端都是 b,左边删掉一个 b、右边删掉两个 b。两层一共删了 6 个字符,原来 9 个减去 6 个,正好剩下中间的 cca 这 3 个。
22. 24收个尾。我们用两个指针从两端往中间夹,每层只要两端字符相同,就把左右各自一整段相同字符都删掉再内移;一旦两端不同或指针交叉就停。s 等于 aabccabba 一路删下来,最短长度是 3。整个过程指针只往里走,线性时间、常数空间。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minimumLength(string s) {
        int i = 0, j = s.size() - 1;
        while (i < j && s[i] == s[j]) {
            while (i + 1 < j && s[i] == s[i + 1]) {
                ++i;
            }
            while (i < j - 1 && s[j] == s[j - 1]) {
                --j;
            }
            ++i;
            --j;
        }
        return max(0, j - i + 1);
    }
};

import java.util.*;
class Solution {
    public int minimumLength(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j && s.charAt(i) == s.charAt(j)) {
            while (i + 1 < j && s.charAt(i) == s.charAt(i + 1)) {
                ++i;
            }
            while (i < j - 1 && s.charAt(j) == s.charAt(j - 1)) {
                --j;
            }
            ++i;
            --j;
        }
        return Math.max(0, j - i + 1);
    }
}

复杂度

面试官可能追问