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.

Solution:
1. Brute Force. Takes O(n^3).
2. Look here for the Leetcode explanation which uses DP. Time and space complexity O(n^2).
    There is also a O(n) solution which we shall see in a later post.

Code:
(same as in the link)

class Solution {
public:
    string longestPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       bool flag[1000][1000] = {false};
       int n=s.length();
       int longestBegin = 0;
       int maxlen = 1;
       int i,j;
       for(i=0; i<n; i++)
       {
           flag[i][i] = true;
       }
       for(i=0; i<n-1; i++)
       {
           if (s[i]==s[i+1])
           {
               flag[i][i+1]= true;
               longestBegin = i;
               maxlen = 2;
           }
       }
       for(int len = 3; len <= n; len++)
       for(i=0; i<n-len+1;i++)
       {
           j=i+len-1;
           if(s[i]==s[j] && flag[i+1][j-1]==true)
           {
               flag[i][j]=true;
               longestBegin = i;
               maxlen = len;
           }
       }
       return s.substr(longestBegin,maxlen);
    }
};