Longest Palindromic Substring With DP O(n^2) Solution JAVA

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

Solution

class Solution {
    public String longestPalindrome(String s) {
        String ans = "";
        int n = s.length();

        if(n==2 && s.charAt(0)==s.charAt(1)){
            return s;
        }
        boolean[][] dp = new boolean[n][n];
        int maxLen = 1;
        int index=0;
        for(int i=0; i<n; i++){
            dp[i][i] = true;
        }

       for(int l = 2; l<=n; l++){
        for(int i=0; i<=n-l; i++){
            int j = i+l-1;

            if(s.charAt(i)==s.charAt(j) && l==2){
                dp[i][j] = true;
                maxLen = 2;
                index  = i;
            }else if(s.charAt(i)==s.charAt(j) && dp[i+1][j-1] == true){
                dp[i][j] = true;
               if(l>maxLen){
                  index = i;
                  maxLen = l;
               }
            }
            else{
                dp[i][j] = false;
            }
        }
       }

        ans = s.substring(index, index+maxLen);
       return ans;
    }
}