My 4ms C solution,O(n^2) time ,O(1) space


  • 0
    H
    char* longestPalindrome(char* s) {
    const int slen = strlen(s);
    int len = 0,mid = 0,tmp,i,j,k;
    for(int t = 0,m = slen >> 1; t <= slen + 1; t++)
    {
        k = m + ((t&1)?-(t>>1):(t>>1));
        for(i = k, j = k + 1, tmp = 0; i >=0 && j < slen &&s[i]==s[j]; i--,j++)
            tmp +=2;
        if(tmp > len) 
            len = tmp,mid = k;
        for(i = k - 1, j = k + 1, tmp = 1; i >=0 && j < slen &&s[i]==s[j]; i--,j++)
            tmp +=2;
        if(tmp > len) 
            len = tmp,mid = k;
        if(len / 2  > slen - k) break;
    }
    char * ret = malloc(sizeof(char)*(len + 2));
    for(int i = 0,j = mid - ((len-1)>>1); i < len; ret[i++] = s[j++]);
    ret[len] = 0;
    return ret;
    }

Log in to reply
 

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