[5] Longest Palindromic Substring

© Jarvus Chen / www.jarvus.net

Description

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"

Required knowledge

Palindromic means a sequence repeat beginning character to the ending part.

Example: abbc, abcba, zasxsaz...

How to copy string in the specific position?

char* s = "abcdefg";
char ans[10];
strncpy(ans, s+2, 3);

//It copy 3 elements from the second position
ans[0]: 'c';
ans[1]: 'd';
ans[2]: 'e';

How to end a char* string?

char* ans = malloc(sizeof(char)*(size+1));
// after assign elements into ans[0] ~ ans[size-1]
ans[size] = '\0';

My solution

My code has two parts. First, input a string and then return whether is a Palindromic sequence or not. 0: FALSE, 1: TRUE.

int isPalindromic(char* s, int length)

In the second part, my method can detect from the beginning (idxL) and check from the last (idxR) is it match. If they are the same char, send to function isPalindromic. Finally, update the newest and largest substring.

char* longestPalindrome(char* s) {
    int size = strlen(s);
    int idxL = 0;
    int idxR = 0;
    int max = 0;
    int maxL = 0;
    int maxR = 0;

    for(int i = 0; i < size-max; i++){
        idxL = s[i];
        // only process the range larger than current max length
        for(int j = size-1; j >= i+max; j--){
            idxR = s[j];
            //printf("%d %c, %d %c\n",i, idxL, j, idxR);
               if ( idxL == idxR ){            
                if ( isPalindromic( &s[i], (j-i+1) ) ){
                    if ( (j-i+1) >= max ){
                        max = (j-i+1);
                        maxL = i;
                        maxR = j;
                    }
                }
            }
        }
    }
    //printf("%d %d %d",max, maxL, maxR);
    char* ans = malloc(sizeof(char)*(max+1));
    strncpy(ans, s+maxL, max);
    ans[max] = '\0';
    return ans;
}
int isPalindromic(char* s, int length){
    for(int i = 0; i < length/2; i++){
        if ( s[i] !=  s[length-1-i] ){
            return 0;
        }
    }
    return 1;
}

Others solution

https://discuss.leetcode.com/topic/23315/my-0ms-c-solution/2

It's looking for a Palindromic sequence center first. i.e., aba, cdc and so on. Then, extend to the both side and calculate its length.

#define strndup(from, n) strncpy(calloc(n + 1, sizeof(char)), from, n)

char* longestPalindrome(char* s) {
    int longest = 1, length = strlen(s);
    char *start = s, *center = s;

    while (center + longest / 2 < s + length) {

        char* b = center, *e = center + 1;
        // count # of chars in the center
        // eg. in ...abbbba..., there are 4 b's in the center
        while(*b == *e) { 
            e++;
        } 

        center = e;

        // count # of steps we can take
        while(b > s && *(b - 1) == *e) {
            --b, e++;
        }

        // eg. in ...tcabbbbacp...
        // and length of cabbbbac is 8, e - b
        if(e - b > longest) { 
            longest = e - b; 
            start = b;
        }
    }

    return strndup(start, longest);
}