Longest Palindromic Substring

leetcode 5. Longest Palindromic Substring

A commom approach: Brute force

Brute force usually will not work in dp problem, but I use two pointers approach to handle bool isPalindromic(), so I think that's why?

Time complexity: O(n^2)

Space complexity: O(n^2)

cpp

class Solution {
public:
    bool isPalindromic(char* a, char* b){
        while(a <= b)
            if(*a++ != *b--)
                return false;
        return true;
    }
    string longestPalindrome(string s) {
        int cnt = 0;
        string res;
        for(int i = 0; i < s.size(); i++){
            for(int j = cnt+1; j <= i; j++){
                //cout << i-j << " " << i << endl;
                if(isPalindromic(&s[i-j],&s[i])){
                    //cout << "true\n";
                    cnt = j;
                    res = s.substr(i-j, j+1);
                }
            }
        }
        if(cnt == 0)
            return s.substr(0,1);
        return res;
    }
};

Runtime: 508 ms, faster than 27.38% of C++ online submissions for Longest Palindromic Substring.

Memory Usage: 24.6 MB, less than 43.09% of C++ online submissions for Longest Palindromic Substring.

Optimized Solution:

I find out that if there's some characters duplicates, it's definitly a Palindromic string and can use it as the middle of current this palindromic string. Also, use it as the middle can only be the maximum, means that we can reduce time playing on duplicate value, like we compute 3 times originally encounter a,a,a, but now, instead do it step-by-step, we use the 2nd 'a' as middle, thus only have to compute once.

cpp

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.empty()) return "";
        if(s.size() == 1) return s;
        
        int min_start = 0, max_len = 1;
        for(int i = 0; i < s.size(); ){
            if(s.size() - i <= max_len / 2)
                break; // if it cannot produce greater max value, just break instead.
            int k = i, j = i;
            while(k+1 < s.size() && s[k] == s[k+1])
                k++;
            i = k+1;
            while(j > 0 && k+1 < s.size() && s[j-1] == s[k+1])
                j--,k++;
            if(k-j+1 > max_len){
                max_len = k-j+1;
                min_start = j;
            }
        }
        
        return s.substr(min_start, max_len);
    }
};

Runtime: 3 ms, faster than 99.72% of C++ online submissions for Longest Palindromic Substring.

Memory Usage: 7.1 MB, less than 92.74% of C++ online submissions for Longest Palindromic Substring.

Longest Palindromic Substring ​

A commom approach: Brute force ​

Optimized Solution: ​

Longest Palindromic Substring

A commom approach: Brute force

Optimized Solution: