Understand the problem:
The problem asks for finding the longest palindromic substring in string S. The problem assumes that there is only one unique longest palindromic substring, and we are asked to return that substring.
Naive Solution:
One straight-forward solution is to check each substring and determine if it is palindromic. So looping over each substring take O(n^2) time and checking each substring takes O(n) time. The total time complexity is O(n^3).
DP Solution:
This question is quite similar to the Palindrome partitioning II, where return the minimum number of cuts such that all substrings are palindrome. The minimum cuts are equal to the longest palindrome. So we can still use the same idea to solve this problem.
In the palindrome partitioning II problem, we used an array dp[i] to indicate the minimum number of cuts from i to the end. However, in this problem, the longest palindromic substring does not always start from the first character of the input string; it can start from anywhere else. So we don't need to maintain an array dp[i] and check the results in dp[0]. Instead, whenever we found string[i, j] is a palindrome, we check its length. If it is the maximum, we keep it. In this way, we only keep the longest palindromic substring. The way to determine if a string from [i, j] is palindromic is the same as before.
Code (Java):
public class Solution {
public String longestPalindrome(String s) {
String longestStr = null;
int maxLen = 0;
if (s == null || s.isEmpty()) return s;
int len = s.length();
boolean[][] palin = new boolean[len][len];
for (int i = len - 1; i >= 0; i--) {
for (int j = i; j < len; j++) {
if ((s.charAt(i) == s.charAt(j) && (j - i) < 2) || (s.charAt(i) == s.charAt(j) && palin[i + 1][j - 1])) {
palin[i][j] = true;
int temp = j - i + 1;
if (temp > maxLen) {
maxLen = temp;
longestStr = s.substring(i, j + 1);
}
}
}
}
return longestStr;
}
}
Discussion:
So we see that both time and space complexity is O(n^2) for this solution.
O(1) Space solution:
We can even develop a O(1) space solution. For a string is palindrome, it must be mirrored across a central point. Here we must consider both the even and odd length of the string. For a string with odd length, e.g. aa, it is palindromic for s[lo] == s[hi] where lo = 0, and hi = 1. For odd length, e.g. aba, lo = 0, and hi = 2. So we can iterate the string and check its left and right points to see if it is mirrored.
Code (Java):
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len <= 1) return s;
int start = 0;
String longestSub = "";
int maxLen = 0;
for (int i = 1; i < len; i++) {
//check the longest palindromic substring with even length;
int lo = i - 1;
int hi = i;
while (lo >= 0 && hi < len && s.charAt(lo) == s.charAt(hi)) {
lo--;
hi++;
}
if ((hi - lo - 1) > maxLen) {
maxLen = hi - lo - 1;
start = lo + 1;
}
// check the longest palindromic substring with odd length
lo = i - 1;
hi = i + 1;
while (lo >= 0 && hi < len && s.charAt(lo) == s.charAt(hi)) {
lo--;
hi++;
}
if ((hi - lo - 1) > maxLen) {
maxLen = hi - lo - 1;
start = lo + 1;
}
}
return s.substring(start, start + maxLen);
}
}
Discussion:
We can see that the solution above has time complexity of (n^2) since each point we need to check its left and right sides. The space complexity is (1).
Summary:
In this post, we learned how to find the longest palindromic substring. It is a classic problem. The DP solution is classic as well. Make sure you can apply it to other DP problems. Actually, there exists another method with time complexity of O(n). It is kind of complicated so we don't cover it here.
Update on 11/26/14:
public class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() <= 1) {
return s;
}
int start = 0;
int len = 1;
for (int i = 0; i < s.length(); i++) {
int curLen = 0;
// For even length
int lo = i;
int hi = i + 1;
while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
curLen += 2;
lo--;
hi++;
}
if (curLen > len) {
len = curLen;
start = lo + 1;
}
// For odd length
lo = i - 1;
hi = i + 1;
curLen = 1;
while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
curLen += 2;
lo--;
hi++;
}
if (curLen > len) {
len = curLen;
start = lo + 1;
}
}
return s.substring(start, start + len);
}
}
Update on 4/7/2019
public class Solution {
/**
* @param s: input string
* @return: the longest palindromic substring
*/
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
int maxLen = 0;
int startIdx = 0;
for (int i = 0; i < s.length(); i++) {
int lenEven = findLongestPalin(s, i, i + 1);
int lenOdd = findLongestPalin(s, i - 1, i + 1) + 1;
if (lenEven > lenOdd && lenEven > maxLen) {
maxLen = lenEven;
startIdx = i - lenEven / 2 + 1;
} else if (lenOdd > lenEven && lenOdd > maxLen) {
maxLen = lenOdd;
startIdx = i - lenOdd / 2;
}
}
return s.substring(startIdx, maxLen + startIdx);
}
private int findLongestPalin(String s, int start, int end) {
int ans = 0;
while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
start--;
end++;
ans += 2;
}
return ans;
}
}
No comments:
Post a Comment