The simple approach is to check each substring whether the substring is a palindrome or not. We can run three loops, the outer two loops pick all substrings one by one by fixing the corner characters, the inner loop checks whether the picked substring is palindrome or not.
Let s be the input string, i and j are two indices of the string. Define a 2-dimension array “table” and let dp[i][j] denote whether a substring from j to i is palindrome, and it is filled in bottom up manner.
The value of dp[i][j] is true, if the substring is palindrome, otherwise false.
public String longestPalindrome(String s) {
if (s ==null|| s.length() <= 1) {
return s;
}
int n = s.length();
boolean[][] dp =newboolean[n][n];
int maxLen = 1; // atleast longest palindrome will have 1 charint start = 0;
int end = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
// Base cases:// - Single character is a palindrome (length 1)if (i == j) {
dp[i][j]=true;
}
// - Two adjacent characters are a palindrome (length 2)elseif (i - j == 1 && s.charAt(i) == s.charAt(j)) {
dp[i][j]=true;
} else {
// Check if the substring between (j + 1) and (i - 1) is a palindrome// and the characters at i and j are the same dp[i][j]= s.charAt(i) == s.charAt(j) && dp[j + 1][i - 1];
}
// Update maxLen and start/end if a longer palindrome is foundif (dp[i][j]&& maxLen < i - j + 1) {
maxLen = i - j + 1;
start = j;
end = i;
}
}
}
return s.substring(start, end + 1);;
}
Now that the DP table is filled, we need to find the longest palindrome based on the True values.
We can see that dp[3][2] = True (substring “bab” is a palindrome).
We also see that dp[1][1] = True (substring “a” is a palindrome, but it’s shorter than “bab”).
Since dp[3][2] represents a longer palindrome (length 3), we update:
maxLen = 3
start = 2 (index of ‘b’ in “bab”)
end = 4 (index of ‘b’ in “bab” - remember indexing starts from 0)
Method 3 - Generate the Palindromes by expanding from middle 🏆#
When we usually check the palindromes, we check it from outward to invward, i.e 2 pointers left and right move towards the centre. What if we start from center and look outward.
For eg. take the string babad. When i = 0, we have b. We cannot expand on left, so b is only palindrome. Lets have i = 1, we get a. Now, we can go both leftwards and rightwards, we get bab as the palindrome now.
So, when we go from point in array, say i, we expand on left and right; So, overall time complexity will be O(n^2).
The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.
Step to generate odd length palindrome: Fix a centre and expand in both directions for longer palindromes.
Step to generate even length palindrome: Fix two centre ( low and high ) and expand in both directions for longer palindromes.
public String longestPalindrome(String s) {
if (s ==null|| s.length() < 1) {
return"";
}
String longest = s.substring(0, 1);
for (int i = 0; i < s.length(); i++) {
// odd length palindrome String tmp = expandFromMiddle(s, i, i);
if (tmp.length() > longest.length()) {
longest = tmp;
}
// even length palindrome tmp = expandFromMiddle(s, i, i + 1);
if (tmp.length() > longest.length()) {
longest = tmp;
}
}
return longest;
}
// Given a center, either one letter or two letter,// Find longest palindromepublic String expandFromMiddle(String s, int begin, int end) {
while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
begin--;
end++;
}
return s.substring(begin + 1, end);
}
public String longestPalindrome(String s) {
if (s ==null|| s.length() < 1) {
return"";
}
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandFromMiddle(s, i, i);
int len2 = expandFromMiddle(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > (end - start)) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
privatestaticintexpandFromMiddle(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}