WikiGalaxy
Longest Palindromic Substring: Introduction
Understanding Palindromes
A palindrome is a string that reads the same forward and backward. The "Longest Palindromic Substring" problem involves finding the longest contiguous substring of a given string that is a palindrome.
Example 1: Center Expansion Method
Center Expansion
The center expansion technique involves expanding around each character (and each pair of characters) to find the longest palindrome centered at that position.
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(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);
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
Console Output:
"bab" or "aba"
Example 2: Dynamic Programming Approach
Dynamic Programming
Using a dynamic programming table, we can store the palindromic status of substrings and build up to the solution.
public String longestPalindromeDP(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int start = 0, maxLength = 1;
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
for (int length = 2; length <= n; length++) {
for (int i = 0; i < n - length + 1; i++) {
int j = i + length - 1;
if (s.charAt(i) == s.charAt(j)) {
if (length == 2) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
if (dp[i][j] && length > maxLength) {
start = i;
maxLength = length;
}
}
}
}
return s.substring(start, start + maxLength);
}
Console Output:
"cbbc"
Example 3: Manacher's Algorithm
Manacher's Algorithm
This algorithm finds the longest palindromic substring in linear time by transforming the string and using a clever observation of palindrome properties.
public String longestPalindromeManacher(String s) {
char[] T = new char[s.length() * 2 + 3];
T[0] = '^';
T[s.length() * 2 + 2] = '$';
for (int i = 0; i < s.length(); i++) {
T[2 * i + 1] = '#';
T[2 * i + 2] = s.charAt(i);
}
T[s.length() * 2 + 1] = '#';
int[] P = new int[T.length];
int center = 0, right = 0;
for (int i = 1; i < T.length - 1; i++) {
int i_mirror = 2 * center - i;
if (right > i) {
P[i] = Math.min(right - i, P[i_mirror]);
}
while (T[i + 1 + P[i]] == T[i - 1 - P[i]]) {
P[i]++;
}
if (i + P[i] > right) {
center = i;
right = i + P[i];
}
}
int maxLength = 0;
int centerIndex = 0;
for (int i = 1; i < P.length - 1; i++) {
if (P[i] > maxLength) {
maxLength = P[i];
centerIndex = i;
}
}
return s.substring((centerIndex - 1 - maxLength) / 2, (centerIndex - 1 + maxLength) / 2);
}
Console Output:
"anana"
Example 4: Brute Force Approach
Brute Force
The brute force approach checks all possible substrings and determines if they are palindromes. This method is not efficient for large strings.
public String longestPalindromeBruteForce(String s) {
int n = s.length();
if (n == 0) return "";
String longest = s.substring(0, 1);
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
String substring = s.substring(i, j + 1);
if (isPalindrome(substring) && substring.length() > longest.length()) {
longest = substring;
}
}
}
return longest;
}
private boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}
Console Output:
"racecar"
Example 5: Optimized Brute Force with Early Exit
Optimized Brute Force
This approach improves the brute force method by adding early exit conditions when a longer palindrome is found, reducing unnecessary checks.
public String longestPalindromeOptimizedBruteForce(String s) {
int n = s.length();
if (n == 0) return "";
String longest = s.substring(0, 1);
for (int i = 0; i < n; i++) {
for (int j = n - 1; j > i; j--) {
if (j - i + 1 <= longest.length()) break;
if (isPalindrome(s.substring(i, j + 1))) {
longest = s.substring(i, j + 1);
break;
}
}
}
return longest;
}
Console Output:
"noon"
