Leetcode 5 Solution

Leetcode Question Link

https://leetcode.com/problems/longest-palindromic-substring

Thinking Process

This is a pretty straightfoward question. There are many solutions to it. The solution I used is just to fix the center point and expand the current substring until it is not a palindromic one. Everytime we have a new palindromic string, we compare it with the current max one. If it is longer, replace it with the current max one.

The only trick here is that the palindtromic string could be an even size or an odd size. For even size, we expand from two positions. For odd size, we expand from one position. There are still many ways to handle this. The way I used was simple to use two pointer, i1 and i2. I walked i1 and i2 using the following logic

i1 == i2 ? i2++ : i1++;

Time & Space Complexity

Assuming N is the size of the string

• Time Complexity: O(N)
• Space Complexity: O(1)

Solution

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        int i1 = 0;
        int i2 = 0;
        int maxl = 1;
        int pos = 0;
        const char* str = s.c_str();

        while (i2 < n)
        {
            int k1 = i1;
            int k2 = i2;

            while (k1 >= 0 && k2 < n)
            {
                if (str[k1] == str[k2])
                    k1--, k2++;
                else
                    break;
            }
            k1++, k2--;

            if (k2 - k1 + 1 > maxl)
            {
                maxl = k2 - k1 + 1;
                pos = k1;
            }

            i1 == i2 ? i2++ : i1++;
        }

        return s.substr(pos, maxl);
    }
};