Provide Best Programming Tutorials

## [LeetCode]5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 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()<2) return s;
int n = s.length();
char[] c = s.toCharArray();

Boolean dp[][] =new Boolean[n][n];
int left = 0, right = 0;
for(int i = n-1;i>=0;i--){
for(int j = i; j<n; j++){
if (j-i < 3) { //base case
dp[i][j] = (c[i] == c[j]);
} else {
dp[i][j] = (c[i] == c[j] && dp[i+1][j-1]);
}
if (dp[i][j] && (right-left <= j-i)) {
left = i;
right = j;
}
}
}
return s.substring(left,right+1);
}
}```

Success

Runtime: 74 ms, faster than 20.61% of Java online submissions for Longest Palindromic Substring.

Memory Usage: 49.6 MB, less than 6.45% of Java online submissions for Longest Palindromic Substring.