5. Longest Palindromic Substring

problem description

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

example

Example 1:

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

Example 2:

Input: "cbbd"
Output: "bb"

algorithm thought

直接用遍历找回文串就行。遍历一次字符串，对每个字符串，将它当作一个回文串的中间，向两边扩散。比较得到最大值

code

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()==0)
            return "";
        int res=0;
        int lm=0,rb=0,size=s.size();
        for(int i=0;i<size;++i){
            int left=i-1;
            int right=i+1;
            while(left>=0&&right<size&&s[left]==s[right]){
                if(right-left>res){
                    lm=left;rb=right;
                    res=right-left;
                }
                right++;left--;
            }
            left=i;right=i+1;
            while(left>=0&&right<size&&s[left]==s[right]){
                if(right-left>res){
                    lm=left;rb=right;
                    res=right-left;
                }
                right++;left--;
            }
        }
        //cout<<lm<<rb;
        return s.substr(lm,res+1);
    }
};

algorithm analysis

最坏情况下，所有字符都是一样的，每次都会进入子循环，时间复杂度是O(n平方)

最好情况下，所有字符都不一样，每次不会进入子循环，时间复杂度是O(n)