Longest Palindromic Substring

Question

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example

Input: "bbbab"
Output: 4

Input: "cbbd"
Output: 2

Solution

• Use Dynamic Programming Approach. set the DP[i][j]as if it is palindrome from i to j. And we have to take care of dp[i+1][j-1] in case if j - 1 < 0 we set j - i <= 2
• Try every possible start point and then spread to find the possible palindrome substring.

Code

// time:O(n^2) 
// space:O(n^2) 
public String longestPalindrome(String s) {
       int n = s.length();
       if (s == null || n == 0) return "";
       String res = "";
       int max = 0;
       boolean[][] dp = new boolean[n][n];
       for (int j = 0; j < n; j++) {
           for (int i = 0; i <= j; i++) {
               // j - i <= 2 为了不让后面j -1出现负数。
               dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i <= 2 || dp[i + 1][j - 1]);
               if (dp[i][j]) {
                   if (j - i + 1 > max) {
                       max = j - i + 1;
                       res = s.substring(i, j + 1);
                   }
               }
           }
       }
       return res;
   }

	// time:O(n^2)
	// space:O(1)
	public int max = 0;
   public String res = "";
   
   public String longestPalindrome(String s) {
       int n = s.length();
       if (s == null || n == 0) return "";
       for (int i = 0; i < n; i++) {
           spreadToLeftAndRight(s, i, i); // ...x...  odd.
           spreadToLeftAndRight(s, i, i + 1); // ...xx...  even.
       }
       return res;
   }
   
   public void spreadToLeftAndRight(String s, int left, int right) {
       while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
           left--;
           right++;
       }
       String str = s.substring(left + 1, right);
       if (str.length() > max) {
           max = str.length();
           res = str;
       }
   }