java - Why my DP algo for Longest Palindromic Substring is slow

Question

Hi I am trying to solve LeetCode Problem number 5 Longest Palindromic Substring. I am using the DP strategy that I increase value in the DP table by 2 if it's an odd palindrome and I increase it by 1 if it's an even one; and I keep track of the largest value in the table. I think my strategy is just O(n^2), but the running time is extremely long, which takes 280 ms. I tried to improve the subString() method by implementing a StringBuilder and append it myself, but it didn't help much. I really don't know why it's taking so long to run my code. Please help.

 class Solution {
    public String longestPalindrome(String s) {
        int size = s.length();
        int dp[][] = new int[size][size];
 
        int len = 1;
        int maxI=0;
        int maxJ=0;
        
        StringBuilder sb=new StringBuilder("");
        for (int j = 0; j < size; j++) {
            for (int i = 0; i <= j; i++) {
                if (i == j) {
                    dp[i][j] = 1;
                } else if(i<j){     
                    if(s.charAt(i) == s.charAt(j)){
                        if((dp[i + 1][j - 1] > 0)){
                            dp[i][j] = dp[i + 1][j - 1] + 2;
                        }if((dp[i][j-1] == 1)){
                             dp[i][j] = 2;
                        }
                    }else {
                        dp[i][j] = 0;
                    }
                }
                if ( len<dp[i][j]||(len==dp[i][j] && j>maxJ) ){
                    len = dp[i][j];
                    maxI= i;
                    maxJ=j;
                }

            }

        }
        return s.substring(maxI, maxJ+1);
    }
}

标签： java