5. Longest Palindromic Substring

My intuition is to use DP. The dp[i] saves the longest valid palindrome and dp[i] = dp[i-1] + 2 if s[i-dp[i-1]-1] == s[i]. However, this state transition formula doesn't cover all cases because palindrome can be odd or even long. The right DP way is to have dp[i][j] true if s[i...j] is a palindrome. So the state transition formula is dp[i][j] = true if s[i] == s[j] && dp[i+1][j-1]. The running time is O(n*n).

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

Another way is scan the string and for each position scan toward two ends and check if any palindrome exists. Particularly, we need to deal with even and odd long palindromes (note they are not exclusive).

1:  class Solution {  
2:  private:  
3:    int maxLen;  
4:    int start;  
5:  public:  
6:    string longestPalindrome(string s) {  
7:      start = 0;  
8:      maxLen = 1;  
9:      for (int i = 0; i < s.size()-1; i++) {  
10:        if (s[i] == s[i+1]) {  
11:          search(s, i, i+1);  
12:        }  
13:        search(s, i, i);  
14:      }  
15:      return s.substr(start, maxLen);  
16:    }  
17:    void search(string s, int i, int j) {  
18:      int l = 1;  
19:      while ((i-l) >= 0 && (j+l) < s.size()) {  
20:        if (s[i-l] != s[j+l]) break;  
21:        l++;  
22:      }  
23:      int len = j-i+2*l-1;  
24:      if (len > maxLen) {  
25:        maxLen = len;  
26:        start = i-l+1;  
27:      }  
28:    }  
29:  };