0ms C solution accepted


  • 0
    L

    char* longestPalindrome(char* s) {

    int i = 0, n = strlen(s);
    int longest = 0, longestx;
    char *str;
    
    if (n == 1)
        return s;
    
    do {
        int k = 1;
        int j = 1;
        
        if (((n - i) * 2 + 1) < longest)
            break;
            
        while (i + k < n && s[i] == s[i+k])
            k++;
            
        while(i - j >= 0 && i + k - 1 + j < n && s[i - j] == s[i + k - 1 + j])
            j++;
        
        if ((j - 1) * 2 + k > longest) {
            longest = (j - 1) * 2 + k;
            longestx = i - (j - 1);
        }
        
        i += k -1 > 0 ? k - 1 : 1;
    } while (i < n - 1);
    
    str = (char *) malloc(longest + 1);
    memcpy(str, s + longestx, longest);
    str[longest] = 0;
    
    return str;
    

    }


  • 0
    W

    this algorithm is O(n^2) but its concise though, especially using

    if (((n - i) * 2 + 1) < longest)  break;
    

    and

    while (i + k < n && s[i] == s[i+k])   k++;
    

    here


Log in to reply
 

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