5 Longest Palindromic Substring ***** 2d - DP

Given a strings, find the longest palindromic substring ins. You may assume that the maximum length ofsis 1000.

Example 1:

Input:
 "babad"

Output:
 "bab"

Note:
 "aba" is also a valid answer.

Example 2:

Input:
 "cbbd"

Output:
 "bb"

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        int len = s.length();
        int max = 0;
        String ans = "";
        boolean[][] dp = new boolean[len][len];
        for (int j = 0; j < len; j++) {
            for (int i = 0; i <= j; i++) {
                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;
                        ans = s.substring(i, j + 1);
                    }
                }
            }
        }
        return ans;
    }
}

dp[i][j] = ((s.charAt(i) == s.charAt(j)) && (j - i <= 2 || dp[i+1][j-1]));

Approach #3 (Dynamic Programming) [Accepted]

To improve over the brute force solution, we first observe how we can avoid unnecessary re-computation while validating palindromes. Consider the case”ababa”. If we already knew that”bab”is a palindrome, it is obvious that”ababa”must be a palindrome since the two left and right end letters are the same.

We defineP(i,j)P(i,j)as following:

P(i,j)={true,false,if the substring Si…Sj is a palindromeotherwise.

Therefore,

P(i,j)=(P(i+1,j−1)Si==Sj)P(i,j)=(P(i+1,j−1) and S​i​​==S​j​​)

The base cases are:

P(i,i)=trueP(i,i)=true

P(i,i+1)=(Si==Si+1)P(i,i+1)=(S​i​​==S​i+1​​)

This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on...

Complexity Analysis

• Time complexity :O(n2)O(n​2​​). This gives us a runtime complexity ofO(n2)O(n​2​​).

• Space complexity :O(n2)O(n​2​​). It usesO(n2)O(n​2​​)space to store the table.

Additional Exercise

Could you improve the above space complexity further and how?

Solution 2 :

Approach #4 (Expand Around Center) [Accepted]

In fact, we could solve it inO(n2)O(n​2​​)time using only constant space.

We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only2n−12n−1such centers.

You might be asking why there are2n−12n−1but notnncenters? The reason is the center of a palindrome can be in between two letters. Such palindromes have even number of letters (such as”abba”) and its center are between the two’b’s.

Time complexity :O(n2).

Since expanding a palindrome around its center could takeO(n)O(n)time, the overall complexity isO(n2).

• Space complexity :O(1)O(1).

class Solution {
    String res = "";
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        for (int i = 0; i < s.length(); i++) {
            helper(s, i, i);
            helper(s, i, i + 1);
        }
        return res;
    }
    public void helper(String s, int left, int right) {
       while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
           left--;
           right++;
       }
        String cur = s.substring(left + 1, right);
        if (cur.length() > res.length()) {
            res = cur;
        }
    }
}