5. Longest Palindromic Substring

, , , ,

Code

Expand Around Center

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
class Solution {
public:
    int expand(string &s, int left, int right){
        while(left >= 0 && right < s.length() && s[left] == s[right]){
            left--;
            right++;
        }
        return right - left - 1;
    }
    string longestPalindrome(string s) {
        int start = 0, max_len = 1;
        for(int i = 0; i < s.length(); i++){
            int odd = expand(s, i, i);
            int even = expand(s, i, i + 1);
            int cur_max = max(odd, even);
            // cout << "i = " << i << ", odd = " << odd << ", even = " << even << "\n";

            if(cur_max > max_len){
                start = i - (cur_max - 1) / 2;
                max_len = cur_max;
                // cout << "start = " << start << ", max_len = " << max_len << "\n";
            }
        }
        return s.substr(start, max_len);
    }
};

Dynamic Programming

if s[i] == s[j] and

  1. i <= j + 2 (the length is 2 or 3)
  2. dp[i + 1][j - 1] is true (the substring inside is a palindrome)

then s[i..j] is a palindrome.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    
    string longestPalindrome(string s) {
        int n = s.length();
        int max_len = 1, start = 0;
        vector< vector<bool> >dp(n, vector<bool>(n, false));
        for(int i = 0; i < n; i++){
            dp[i][i] = true;
            for(int j = 0; j < i; j++){
                if(s[j] == s[i] && (i <= j+2 || dp[j+1][i-1])){
                    dp[j][i] = true;
                    if(i - j + 1 > max_len){
                        start = j;
                        max_len = i - j + 1;
                    }
                }
            }
        }
        return s.substr(start, max_len);
    }
};

Brute Force

  • O(n^3) time
  • still accepted though
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        for(int len = n; len > 1; len--){
            for(int i = 0; i + len - 1 < n; i++){
                int j = i, k = i + len - 1;
                bool valid = true;
                while(j < k && valid){
                    if(s[j] != s[k]) valid = false;
                    j++, k--;
                }
                if(valid) return s.substr(i, len);
            }
        }
        return s.substr(0, 1);
    }
};