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"
solution: using dp: i : start index, j : ending index
given fixed size(number of subString), check each substring(from s)
class Solution {
public String longestPalindrome(String s) {
//nature structure
//given fixed step(number,size), check each subString
//dp -- from 0 to n-1
int max = 0;
String res = "";
int n = s.length();
boolean[][] dp = new boolean[n][n];
for(int i = 0; i<n;i++){//fixed number
for(int j = 0; j+i<n; j++){//start inex
if(s.charAt(j) == s.charAt(j+i)){
if(i<2 || dp[j+1][j+i-1]){ // 0 or 1
dp[j][j+i] = true;
dp[j+i][j] = true;
if(max<i+1){
max = i+1;
res = s.substring(j,j+i+1);
}
}
}
}
}
//System.out.println(max);
return res;
}
}
more solution here
https://leetcode.com/problems/longest-palindromic-substring/solution/