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.

Example:

Input:
 "babad"

Output:
 "bab"

Note:
 "aba" is also a valid answer.

Example:

Input:
 "cbbd"

Output:
 "bb"

思路：循环，然后在每个位置生长

public class Solution {
    public int lo,maxLen;

    public String longestPalindrome(String s) {
        if (s==null||s.length()<2){
            return s;
        }

        for (int i=0;i<s.length();i++){
            expandPalindrome(s,i,i);
            expandPalindrome(s,i,i+1);
        }
        return s.substring(lo,lo+maxLen);
    }

    public void expandPalindrome(String s, int low, int high){
        while(low>=0&&high<s.length()&&s.charAt(low)==s.charAt(high)){
            low--;
            high++;
        }

        if (high-low-1>maxLen){
            lo = low+1;
            maxLen = high-low-1;
        }
    }
}

C++ code

class Solution {
public:
    int lo, maxLen;

    string longestPalindrome(string s) {
        if (s.empty() || s.size()<2) return s;

        for (int i=0;i<s.size();i++){
            expandPalindrome(s,i,i);
            expandPalindrome(s,i,i+1);
        }

        return s.substr(lo,maxLen);
    }

    void expandPalindrome(string s, int left, int right){
        while(left>=0 && right<s.size() && s[left]==s[right]){
            left--;
            right++;
        }

        if (right-left-1 > maxLen){
            lo = left+1;
            maxLen = right-left-1;
        }
    }
};