LeetCode 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, and there exists one unique longest palindromic substring.

The original problem is here.

The original code is here.

My Solution

I solve this problem in C++, as below:

*Longest Palindromic Substring 
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
using namespace std;

class Solution {
    string longestPalindrome(string s) {
        int len = s.length();
        if(len <= 1)
            return s;
        string str;
        int maxLen = 0;
        bool p[1000][1000] = {0};
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                if(s[i] == s[j] && (j-i<=2 || p[i+1][j-1])){
                    p[i][j] = true;
                    int sublen = j - i +1;
                    if(sublen > maxLen){
                        str = s.substr(i,sublen);
                        maxLen = sublen;
                    p[i][j] = false;
        return str;

int main(){
    string str("aaabaaaa");
    Solution s;
    //string new_str = s.inverse(str);
    //cout<<"new str="<<new_str<<endl;
    string substr = s.longestPalindrome(str);


To solve the problem, dynamic program is used. P[i][j] labels whether the substr(i,j) is palindrome or not.