# Wrong answer on input "aaabaaaa" but works fine in Ideone

• I am trying to do this in O(n^2) with auxiliary space of O(n^2), which is bool table[1000][1000]. I find out the starting index and the maxLength of the longest Palindromic substring starting from substrings of length 2 to n. It gives correct output in Ideone (http://ideone.com/FqmmNU) and CodeBlocks, but here :
Input: "aaabaaaa"
Output: "aaabaaaa"
Expected: "aaabaaa" .

``````char* longestPalindrome(char* s) {
int n = strlen(s) ;
if(n <= 1)
return s ;
int i, j, l ;
bool table[1000][1000] ;
for(i = 0 ; i < n ; i++)
table[i][i] = true ;
int start = 0, maxLength = 1 ;

for(l = 2 ; l <= n ; l++) {
for(i = 0 ; i < n-l+1 ; i++) {
j = i+l-1 ;
if(l == 2) {
if(s[i] == s[j]) {
table[i][j] = true ;
start = i ;
maxLength = 2 ;
}
}
else {
if(table[i+1][j-1] && (s[i] == s[j]) ) {
table[i][j] = true ;
if(l > maxLength) {
start = i ;
maxLength = l ;
}
}
}
}
}
char *pal = (char *)malloc((maxLength+1) * sizeof(char) ) ;
for(i = start, j = 0 ; i <= start + maxLength - 1 ; i++, j++)
pal[j] = s[i] ;
pal[j] = '\0' ;
return pal ;
}``````

• You should initialize the array, maybe some compilers will do it for you , others will not. It's safe to do it yourself

``````bool table[1000][1000] ;
memset(table,false,sizeof(table));
``````

BTW, I think 'l' is not a good variable. It's difficult to tell 'l' from '1'.

• Thanks a lot for the answer.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.