/**
 * Name: Longest Palindromic Substring
 * Number: 5
 * Tag: DP
 * Idea: dp(i, j)) represents whether s(i,j) is palindromic, check each palindromic substring, record the max length
 * Time Comlplexity: O(n ^ 2)
 * Space Comlexity: O(n ^ 2)
**/
public class Solution {
    public String longestPalindrome(String s) {
        String res = null;
        if (s == null || s.length() == 0) return res;
        int len = s.length();
        //definition: dp[i][j] represents whether s(i,j) is palindromic (j >= i)
        boolean[][] dp = new boolean[len][len];
        
        //formula
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <=2 || dp[i + 1][j - 1]);
                //for each palindromic substring, save the maxLenth
                if (dp[i][j] && (res == null || j - i + 1 > res.length())) {
                    res = s.substring(i, j + 1);
                }      
            }
        }
        //result
        return res;
    }
}
@@ -235,17 +235,59 @@
 O(n %5E 2)
-%0A
+%5BDP%5D O(1)%5BTow Pointers%5D%0A**/%0A%0A/** DP VERSION
 **/%0Apubl
@@ -776,16 +776,17 @@
 j - i %3C=
+ 
 2 %7C%7C dp%5B
@@ -1087,8 +1087,960 @@
 %0A    %7D%0A%7D
+%0A%0A/** Two Pointers VERSION **/%0Apublic class Solution %7B%0A    private int start, maxLen;%0A    public String longestPalindrome(String s) %7B%0A       if (s == null %7C%7C s.length() == 0) return null;%0A       %0A       for (int i = 0; i %3C s.length(); i++) %7B%0A           extendPalindrome(s, i, i); //Odd: treat s.chatAt(i) as a center, try to extend Palindrome from the center%0A           extendPalindrome(s, i, i + 1); // Even: treat s.chatAt(i, i + 1) as a center%0A       %7D%0A       return s.substring(start, start + maxLen);%0A    %7D%0A    private void extendPalindrome(String s, int centerStart, int centerEnd) %7B%0A        while (centerStart %3E= 0 && centerEnd %3C s.length() && s.charAt(centerStart) == s.charAt(centerEnd)) %7B%0A            centerStart--;%0A            centerEnd++;%0A        %7D%0A        if (maxLen %3C centerEnd - centerStart - 1) %7B%0A            maxLen = centerEnd - centerStart - 1;%0A            start = centerStart + 1;%0A            //end = centerEnd - 1;%0A        %7D%0A    %7D%0A%7D

add 2pointers-version solution