5. Longest Palindromic Substring

问题

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

例子

**Input: **"babad"
**Output: **"bab"
**Note: **"aba" is also a valid answer.

Input: "cbbd"
**Output: **"bb"

分析

遍历字符串。从当前字符向两边扩展，找到一个局部最长的回文字符串，再更新全局的最长的回文字符串的长度即可。

要注意回文字符串要分成两种类型：

• 长度为奇数，例如acbdbca，ddddd。对称轴为一个字符；
• 长度为偶数，例如acbbca，dddddd。对称轴为两个相同的字符

要点

• 从当前字符向两边扩展
• 回文字符串分类

时间复杂度

O(n^2)

空间复杂度

O(1)

代码

class Solution {
public:
    // 从当前字符向两边扩展，找到一个局部最长的回文字符串
    int expandFromCenterLength(const string &s, int beg, int end)
    {
        while (beg >= 0 && end < s.length() && s[beg] == s[end]) 
        {
            beg--;
            end++;
        }
        
        return end - beg - 1;
    }
    
    string longestPalindrome(string s) {
        int beg = 0, end = 0;
        for (int i = 0; i < s.length(); i++)
        {
            int len1 = expandFromCenterLength(s, i, i); // 类型1，长度为奇数的回文字符串
            int len2 = expandFromCenterLength(s, i, i + 1); // 类型2，长度为偶数的回文字符串
            int len = max(len1, len2);
            if (len > end - beg + 1)
            {
                beg = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        
        return s.substr(beg, end - beg + 1);
    }
};