Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: "cbbd"
Output: "bb"
Last updated
Was this helpful?
Was this helpful?
/**
* Time complexity : O(n^3)
* Space complexity : O(1)
*/
class Solution {
public String longestPalindrome(String s) {
int maxLen = 0, start = 0, n = s.length();
for(int i = 0; i < n; i++) {
for(int j = i+1; j <= n; j++) {
if((j-i) > maxLen && isPalindrome(s.substring(i, j))) {
maxLen = j-i;
start = i;
}
}
if(maxLen == n) break;
}
return s.substring(start, start+maxLen);
}
public static boolean isPalindrome(String str) {
int n = str.length();
for(int i = 0; i < n/2; i++) {
if(str.charAt(i) != str.charAt(n-i-1)) return false;
}
return true;
}
}/**
* Time complexity : O(n^2). Since expanding a palindrome around its center
* could take O(n) time, the overall complexity is O(n^2).
* Space complexity : O(1).
*/
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
if(s == null || n == 0) return "";
int start = 0, end = 0;
for(int i = 0; i < n; i++) {
int l1 = expandAroundCenter(s, i, i);
int l2 = expandAroundCenter(s, i, i+1);
int len = Math.max(l1, l2);
if((end-start) < len) {
start = i - (len-1)/2;
end = i + (len/2);
}
}
return s.substring(start, end+1);
}
private int expandAroundCenter(String str, int left, int right) {
while(left >= 0 &&
right < str.length() &&
str.charAt(left) == str.charAt(right)) {
left--;
right++;
}
return right-left-1;
}
}/**
* Time complexity : O(n^2). This gives us a runtime complexity of O(n^2).
* Space complexity : O(n^2). It uses O(n^2) space to store the table.
*/
class Solution {
public String longestPalindrome(String s) {
if(s == null || s.isEmpty()) return "";
char[] sCharArr = s.toCharArray();
int n = s.length();
boolean[][] dp = new boolean[n][n];
int start = 0, maxLen = 1;
for(int i = 0; i < n; i++) {
dp[i][i] = true;
}
for(int i = 0; i < n-1; i++) {
if(sCharArr[i] == sCharArr[i+1]) {
dp[i][i+1] = true;
start = i;
maxLen = 2;
}
}
for(int len = 3; len <= n; len++) {
for(int i = 0; i < n-len+1; i++) {
int j = i+len-1;
if(sCharArr[i] == sCharArr[j] && dp[i+1][j-1]) {
dp[i][j] = true;
if(len > maxLen) {
start = i;
maxLen = len;
}
}
}
}
return s.substring(start, start+maxLen);
}
}