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

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

**Example 1:**

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

**Example 2:**

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

**Constraints:**

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

![](https://cdn.hashnode.com/uploads/covers/65a34f483490f72202261228/22d9fd9e-d6e9-4128-b1b5-1847779bd086.png align="center")

## Solution

```java
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;
    }
}
```