[LeetCode] Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd" Output: "bb"

Example 3:

Input: s = "a" Output: "a"

Example 4:

Input: s = "ac" Output: "a"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

class Solution {
public:
    string longestPalindrome(string s) {
        string palindrome = "";
        int n = s.length();
        if (n < 2)
        {
            return s;
        }
        
        n = (n * 2) + 1;
        int pals[n];
        memset(pals, 0, sizeof(int) * n);
        pals[0] = 0, pals[1] = 1;
        int centreIndex = 1, rightIndex = 2;
        int maxPalLen = 0, maxCentreIndex = 0;
        int left, diff, start, end;
        
        for (int right = 2; right < n; right++)
        {
            left = (2 * centreIndex) - right;
            diff = (rightIndex - right);
            
            if (diff > 0)
            {
                pals[right] = min(pals[left], diff);
            }
            
            while (((right + pals[right]) < n &&
                    (right - pals[right]) > 0) &&
                   (((right + pals[right] + 1) % 2 == 0) ||
                    (s[(right + pals[right] + 1) / 2] ==
                     s[(right - pals[right] - 1) / 2])))
            {
                pals[right]++;
            }
            
            if (pals[right] > maxPalLen)
            {
                maxPalLen = pals[right];
                maxCentreIndex = right;
            }
            if (right + pals[right] > rightIndex)
            {
                centreIndex = right;
                rightIndex = (right + pals[right]);
            }
        }
        
        start = (maxCentreIndex - maxPalLen) / 2;
        end = start + maxPalLen - 1;
        
        for (int i = start; i <= end; i++)
        {
            palindrome += s[i];
        }
        
        return palindrome;
    }
};