Leetcode Longest Palindromic Substring problem solution in C programming

In the Leetcode Longest Palindromic Substring problem solution in C programming Given a string s, return the longest palindromic substring in s.

Leetcode Longest Palindromic Substring problem solution in C programming

char * longestPalindrome(char * s){
    int pLength = strlen(s) + 1 + strlen(s) + 2;
    int pStr[pLength];
    int p[pLength];
    
    pStr[0] = '@';
    pStr[pLength - 1]  = '%';
    
    for(int i = 1; i < pLength - 1; i++){
        if(i % 2){
            pStr[i] = '#';
        }else{
            pStr[i] = s[i/2 - 1];
        }
    }
    
    int iCenter = 0, iRadius = 0, iMirror = 0 ,iRight = 0, palindromeIndexStart = 0, palindromeMax = 0;
    
    for(int i = 1; i < pLength - 1; i++){
        iRight = iCenter + iRadius;
        iMirror = 2 * iCenter - i;
        p[i] = 0;
        
        if(i <= iRight){ 
            if(p[iMirror] <= iRight - i){
                p[i] = p[iMirror];
            }else{
                p[i] = iRight - i;
            }  
        }
        
        while(pStr[i + p[i] + 1] == pStr[i - p[i] - 1]){
             p[i] += 1;
        }
        
        if((i + p[i]) > iRight){
            iCenter = i;
            iRadius = p[i];
        }

        if(p[i] > palindromeMax){
            palindromeMax = p[i];
            palindromeIndexStart = (i - p[i])/2;
        }
    }
    
    char * retChar = (char *)alloca(palindromeMax + 1);
    retChar[palindromeMax] = 0;
    strncpy(retChar, s+palindromeIndexStart, palindromeMax);
    
    return retChar;
}

Also read,

By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.

Leave a Reply

Your email address will not be published. Required fields are marked *