https://leetcode.com/problems/longest-palindromic-substring/#/description
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example:
Input: "cbbd" Output: "bb"
Sol 1:
DP.
State transition equation:
The state is f(i, j) , it means the state transition equation in interval [i,j].
The next status is based on the previous status. We expand inner block by 1 char at a time.
public class Solution {
public String c(String s) {
// DP
// Time O(n2) Space O(n^2)
final int n = s.length();
final boolean [][] f = new boolean [n][n];
int maxLen = 1, start = 0; // The start of the longestPalindrome
for (int i = 0; i < n; i++){
f[i][i] = true;
for(int j = 0; j < i; j++){
f[j][i] = (s.charAt(j) == s.charAt(i) && (i - j < 2 || f[j+1][i-1]));
if (f[j][i] && maxLen < (i-j+1)){
maxLen = i - j + 1;
start = j;
}
}
}
return s.substring(start, start + maxLen);
}
}
Sol 2:
Manacher algorithm in Python O(n)
https://discuss.leetcode.com/topic/10484/manacher-algorithm-in-python-o-n
WIKI