[LeetCode 5] Longest Palindromic Substring

Wow, this one is a beast – also took me an entire afternoon.

The problem is: given a string, find the longest palindromic substring.

The first approach I thought of was brute force – just get it working first.

How to brute force? My initial idea was: Use a fixed function check to determine if a string is a palindrome. If s is a palindrome, we’re done. Otherwise, check s(0, s.length()-2) and s(1, s.length()-1).

I wrote this code and tested it – works fine for short strings. But thinking about it, the complexity is way too high, especially for slightly longer strings.

Sure enough, it timed out.

TLE means the approach is wrong – time to rethink.

Let’s try the reverse approach: First check if s[i] is a palindrome, then expand by 1 on each side. Then check if s[i], s[i+1] is a palindrome, then expand by 1 on each side. The two cases are needed because of the odd/even length distinction.

OK, this should optimize the time for most cases.

But still TLE. However, we’re getting closer to the solution.

Here’s the next insight: we don’t actually need to expand by 1 each time. If we’ve already found a palindrome of length sum, when we enumerate the next center point, we can start expanding from sum/2. And that got AC!

The few WAs were just boundary issues.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    int sum;
    int step;
    string ans;
    string longestPalindrome(string s) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        sum = 0;
        for(int i = 0;i < s.length();i++)
        {
            step = sum/2;
            if(i-step < 0 || i+step >= s.length())
                continue;
            func(s,i-step,i+step);
        }
        for(int i = 0;i < s.length();i++)
        {
            step = sum/2;
            if(i-step < 0 || i+step+1 >= s.length())
                continue;
            func(s,i-step,i+1+step);
        }
        return ans;
    }
    void func(string s,int x,int y)
    {
        if(x < 0 || y > s.length()-1)return;
        if(checkp(s.substr(x,y-x+1)))
        {
            if(sum < y-x+1)
            {
                sum = y-x+1;
                ans = s.substr(x,y-x+1);
            }
            func(s,x-1,y+1);
        }
    }
    bool checkp(string s)
    {
        int i = 0;
        int j = s.length() - 1;
        while(i <= j)
        {
            if(s[i] != s[j])
                return false;
            i++;
            j--;
        }
        return true;
    }
};