LeetCode高频题5：最长回文子串，利用马拉车manacher算加速

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

之前咱们就讲过的：
【1】manacher算法：马拉车算法：返回字符串s的最长回文子串长度

---

文章目录

• LeetCode高频题5：最长回文子串，利用马拉车manacher算加速
• • @[TOC](文章目录)
• 题目
• 一、审题
• 笔试AC暴力解，先转马拉车字符串，然后在马拉车字符串上统计最长回文半径
• 面试最优解：马拉车算法manacher算法
• 总结

题目

给你一个字符串 s，找到 s 中最长的回文子串。

---

一、审题

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

笔试AC暴力解，先转马拉车字符串，然后在马拉车字符串上统计最长回文半径

啥是马拉车字符串？看文章【1】

看本题之前，一定要把【1】学透了，才能来看本题！！！
看本题之前，一定要把【1】学透了，才能来看本题！！！
看本题之前，一定要把【1】学透了，才能来看本题！！！

【1】manacher算法：马拉车算法：返回字符串s的最长回文子串长度

s先转马拉车字符串为str（带#的字符串）
然后位置i遍历，统计i的最长回文半径放入pArr
把最长回文中心用maxC记录，就知道我们从C出发，左边扩多少个，右边扩多少个，截取拼接就是结果

比如下图，s=aba，转str
来到i=3位置是最大回文中心C
最大回文半径是max=4
最大回文长度len=max-1=3
所以从C=3开始往左数3，右数3
中间间隔2,取原串那些字符即可

//暴力解，简单，来到i位置，向左右倒腾查呗
        public String longestPalindrome1(String s) {
            if (s == null || s.length() == 0) return null;
            //暴力解也好，还是优化解也罢，都需要将原始串变化为manacher串
            //往前后，中间插一个特殊的字符：#，方便避免偶数串找不到中心对称轴
            //每个位置i为中心，去做回文检查，找到长度最大的那串，记录下来，然后更新

            char[] str = changeTomanacherString(s);
            int[] pArr = new int[str.length];//每个位置i的回文半径
            int C = 0;//回文最长的中心
            int max = 1;//回文半径

            for (int i = 0; i < str.length; i++) {
                int j = 1;
                while (i - j >= 0 && i + j <str.length && str[i - j] == str[i + j]){
                    if (j + 1 > max) C = i;//更新最大回文中心的位置
                    max = Math.max(max, j + 1);//最大回文长度
                    j++;
                }
                pArr[i] = max;//每次都取最大回文半径
            }

            //char[] res = new char[s.length()];
            String res = "";
            int index = 0;
            //根据最大的回文中心C和回文半径的大小决定要那些数字
            for (int i = C - pArr[C] + 2; i < C + pArr[C]; i+= 2) {
                res += str[i];
            }

            return res;
        }

        //转换为适合处理的manacher串
        public char[] changeTomanacherString(String s) {
            char[] res = new char[(s.length() << 1) + 1];
            char[] str = s.toCharArray();

            for (int i = 0; i < str.length; i++) {
                res[i << 1] = '#';//偶数位置
                res[(i << 1) + 1] = str[i];//奇数位置
            }
            res[res.length - 1] = '#';//最后一个

            return res;
        }

测试一把：

    public static void test(){
        Solution solution = new Solution();

        String  ans2 = solution.longestPalindromeReview("ab12321ts");
        if (ans2 != null) for (int i = 0; i < ans2.length(); i++) {
            System.out.print(ans2.charAt(i) +" ");
        }
        System.out.println();
        ans2 = solution.longestPalindrome1("ab12321ts");
        if (ans2 != null) for (int i = 0; i < ans2.length(); i++) {
            System.out.print(ans2.charAt(i) +" ");
        }
    }

    public static void main(String[] args) {
        test();
    }

1 2 3 2 1 
1 2 3 2 1 

暴力解就看看理解本题的意思就行
重要的是下面的马拉车算法manacher算法

复杂度嘛，最次就是来到i，还得往两边扩全部，比如aaaaaa啥的
整体就是外围i走一个o(n)
内部while可能还需要走一波o(n)
最次就是o(n^2)复杂度

---

面试最优解：马拉车算法manacher算法

咱们之前文章说过【1】manacher算法：马拉车算法：返回字符串s的最长回文子串长度

在那，咱们是求最长回文子串的长度

//复习manacher算法
    public static int manacherReview(String s){
        if (s.equals("") || s.length() == 0) return 0;
        int max = Integer.MIN_VALUE;//先默认负无穷
        
        //s填写虚轴符号#
        char[] str = tomanacherString(s);
        int N = str.length;//新s的长度，也会是pArr的长度
        int[] pArr = new int[N];

        //初始化R,C
        int C = -1;
        int R = -1;//此前已经扩到的最右边界

        //i从0--N-1更新max
        for (int i = 0; i < N; i++) {
            //1--是不是当i>R时，最次pArr[i]=1，就是i字符自己呗【情况1呗】
            //2--否则当i<=R时，咱们**先扩1个基础步骤**，取pArr[i]=min(2C-i，R-i)，
            //**说白了就是要舍弃pArr[i]这么多长度，不要重复对比了**
            //2C-i代表啥呢？i的对称位置i1的回文半径，比较小，求法就是2C-i，你记住就行。
            //R-i代表啥呢？上面情况【2】的（2）（3）中i的对称位置i1的回文半径，就是R-i这么多，咱们不要1，
            //以上几个基础步骤啊，直接统一成依据代码
            pArr[i] = i > R ? 1 : Math.min(2 * C - i, R - i);
            //3--咱们之后才**暴力往外扩，能扣就让pArr[i]++**
            while (i - pArr[i] >= 0 && i + pArr[i] < N){
                //i想外扩的话，这俩位置不能越界
                //如果他俩相等，半径++
                if (str[i - pArr[i]] == str[i + pArr[i]]) pArr[i]++;
                else break;//一旦不能扩了，直接退出
            }

            //4--每次扩完，都需要更新R,C,max，每个i可能都是未来的新的更远的C
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;//新边界来了
            }
            max = Math.max(max, pArr[i]);//带有#的s的最长回文半径
        }

        return max - 1;//结果怎么推的看文章解释
    }

细节，你一定要去看，你只要看了上面文章【1】，才能理解本题的解法，一模一样

今天LeetCode本题是求最长回文子串，要求这个串本身，

因此呢，也很简单
之前求的时候，咱们保存了最大长度那个max，而今天咱们还需要一个变量，将那个最长回文子串的首位置记录下来
有了首位置start，回文子串长度max-1，咱们就知道要截取哪一段了【通过substring(a,b)【左闭右开的】】

比如：

class Solution {
    //转换为适合处理的manacher串
        public char[] changeTomanacherString(String s) {
            char[] res = new char[(s.length() << 1) + 1];
            char[] str = s.toCharArray();

            for (int i = 0; i < str.length; i++) {
                res[i << 1] = '#';//偶数位置
                res[(i << 1) + 1] = str[i];//奇数位置
            }
            res[res.length - 1] = '#';//最后一个

            return res;
        }

    //用substring函数
        //优化算法：manacher算法，马拉车，专门解决回文串，找最长回文串的问题
        //manacher的思路非常清晰，而且要精简代码，缕清那几个步骤，叠加处理
        public String longestPalindrome(String s){
            if (s == null || s.length() == 0) return null;

            char[] str = changeTomanacherString(s);//加#
            int[] pArr = new int[str.length];//每个i的回文半径
            int C = -1;
            int R = -1;//最右边位置的R再右一个
            int max = Integer.MIN_VALUE;//最大回文长度
            int maxC = 0;//记录最大回文长度C的位置
            //目标，填pArr，然后找最大回文串的中心，根据目前i的和i的对称位置pArr信息来确定i的回文半径信息
            for (int i = 0; i < str.length; i++) {
                //扩基础步骤，i>R暴力扩1步，否则看R-i和2C-i的回文半径，先扩
                pArr[i] = i >= R ? 1 : Math.min(pArr[2 * C - i], R - i);//这里R是代表回文最右位置的下一个位置
                //这是几种情况的第一步：i>R的话，还需要继续扩，我自己的长度先算1，或者i<=R,但是
                //i对称位置的回文区域恰好压线，还需要继续扩，我自己的长度先算为R-i，
                //或者对称点的回文半径在R外，我扩不动，就此为止
                //i<R时，上一次回文串的对称位置C，2C-i就是当前i关于C的对称位置
                while (i - pArr[i] > -1 && i + pArr[i] < str.length){//再检查后续能否扩动
                    if (str[i - pArr[i]] == str[i + pArr[i]]) pArr[i]++;//回文半径能扩的动
                        //这里就直接扩到不用验证的区域，省事
                    else break;//一旦扩不动，退出
                }
                //更新最右的回文点，回文右边界，更新中心——这里是马拉车算法的核心更新点
                if (i + pArr[i] > R){
                    C = i;
                    R = i + pArr[i];//最右边
                }

                //记住下面定时max先更新，保证i是max的中心
                if (pArr[i] > max) maxC = i;//记录最长回文串的中心位置——这个可是2倍长那个串的中心，需要/2？
                max = Math.max(max, pArr[i]);//更新最大的回文半径长度

            }

            //每个字符操作完之后回文中心知道了，回文长度也知道了，那起点终点就知道
            maxC = maxC >> 1;//需要除2来保证恢复对应原串的位置
            int len = max - 1;
            int start = maxC - (len >> 1);//len要把中心减掉
            int end = start + len;//+1因为左闭右开的

            return s.substring(start,end);
        }
}

注意啊！
代码中的maxC记录的是含#的2N+1长度的字符串的回文中心，需要最后除2才能把回文中心映射到原串s中
比如：s=abbd
转化为马拉车字符串：str=#a#b#b#d
看下图，根据马拉车算法求得最大回文串的回文中心为maxC=4，但是这是str的最大回文中心
maxC/2才是s的回文中心2
最大回文长度是maxR-1，然后len=2,【这为啥一定要看上面文章【1】】

然后求应该截取字符串的start=maxC-(len/2)
终点是end=start+len
[start,end）
截取的是左闭，右开的字符串
把bb拿到就是结果

看LeetCode测试结果：


随便测试都行：

    public static void test(){
        Solution solution = new Solution();

        String  ans2 = solution.longestPalindromeReview("ab12321ts");
        if (ans2 != null) for (int i = 0; i < ans2.length(); i++) {
            System.out.print(ans2.charAt(i) +" ");
        }
    }

    public static void main(String[] args) {
        test();
    }

1 2 3 2 1 

总之，本题最重要的马拉车算法manacher算法，
一定要一定要一定要把基础文章【1】学会了，才能破解本题！！！
一定要一定要一定要把基础文章【1】学会了，才能破解本题！！！
一定要一定要一定要把基础文章【1】学会了，才能破解本题！！！

【1】manacher算法：马拉车算法：返回字符串s的最长回文子串长度

本质一样的

马拉车算法复杂度多少呢？
i遍历一遍，但是每次有i的对称位置2C-i的信息，咱们能秒杀加速这个求出pArr[i]，因此不像暴力解那样，内部还需要o(n）求这个半径
内部只需要o(1)速度搞定

所以整体复杂度o(n)
速度够快吧，你看了LeetCode测试那了没，超过95%的算法大佬！成为最优解！！

---

总结

提示：重要经验：

1）马拉车manacher算法的核心在利用i位置对称位置2c-i的回文半径，加速求得i的回文半径，每次把最大回文中心更新给maxC，回文半径更新给pArr，最大回文右边界回文给R
2）最后马拉车算法的maxC，需要除2对应映射给原串s，然后求start和end，用substring截取即可。
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。