Introduction
The Longest Palindromic Substring is a classic problem that tests your understanding of strings, dynamic programming, and optimization techniques. A palindrome reads the same forward and backward, and the problem asks for the longest contiguous palindromic substring in a given string. This post will explore various approaches to solve Longest Palindromic Substring Leetcode problem, from basic to advanced, with Java implementations for each.
Problem Statement
Given a string s
, return the longest palindromic substring in s
.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Constraints:
1 <= s.length <= 1000
s consist of only digits and English letters.
1. Brute Force Solution
The simplest way to solve the problem is by checking every possible substring and determining if it’s a palindrome. If it is, keep track of the longest one found.
Algorithm
- Generate all possible substrings.
- Check if each substring is a palindrome.
- Track the longest palindromic substring.
Java Implementation
public class LongestPalindromicSubstring {
// Function to check if a string is a palindrome
private static boolean isPalindrome(String str) {
int left = 0, right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
// Brute force approach
public static String longestPalindromeBruteForce(String s) {
int maxLength = 0;
String longest = "";
int n = s.length();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
String substring = s.substring(i, j);
if (isPalindrome(substring) && substring.length() > maxLength) {
maxLength = substring.length();
longest = substring;
}
}
}
return longest;
}
public static void main(String[] args) {
String s = "babad";
System.out.println("Longest Palindromic Substring (Brute Force): " + longestPalindromeBruteForce(s));
}
}
Time Complexity: O(n³) – Due to checking all substrings and verifying each for palindrome.
Space Complexity: O(1) – No extra space is used except variables.
2. Expanding Around the Center
A better solution is to leverage the fact that a palindrome mirrors around its center. Instead of checking all substrings, we expand around each center and keep track of the longest palindrome found.
Algorithm
- Iterate through the string, treating each character and pair of consecutive characters as a potential center.
- Expand outwards while the substring is a palindrome.
- Track the longest palindrome.
Java Implementation
public class LongestPalindromicSubstring {
// Function to expand around the center
private static String expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return s.substring(left + 1, right);
}
// Expand Around Center approach
public static String longestPalindromeCenterExpand(String s) {
if (s == null || s.length() < 1) return "";
String longest = "";
for (int i = 0; i < s.length(); i++) {
String odd = expandAroundCenter(s, i, i); // Odd-length palindromes
String even = expandAroundCenter(s, i, i + 1); // Even-length palindromes
if (odd.length() > longest.length()) longest = odd;
if (even.length() > longest.length()) longest = even;
}
return longest;
}
public static void main(String[] args) {
String s = "cbbd";
System.out.println("Longest Palindromic Substring (Center Expand): " + longestPalindromeCenterExpand(s));
}
}
Time Complexity: O(n²) – Each center is expanded at most n times.
Space Complexity: O(1) – No additional space needed.
3. Dynamic Programming Solution
This solution uses a 2D table to store whether a substring is a palindrome. If dp[i][j]
is true, the substring s[i...j]
is a palindrome.
Algorithm
- Initialize a 2D boolean array
dp
. - Fill the table based on substring length:
- A single character is always a palindrome.
- A two-character substring is a palindrome if both characters are the same.
- For longer substrings, use
dp[i + 1][j - 1]
to decide ifdp[i][j]
should be true.
- Track the longest palindrome.
Java Implementation
public class LongestPalindromicSubstring {
// Dynamic Programming approach
public static String longestPalindromeDP(String s) {
int n = s.length();
if (n == 0) return "";
boolean[][] dp = new boolean[n][n];
String longest = "";
for (int length = 0; length < n; length++) {
for (int i = 0; i + length < n; i++) {
int j = i + length;
if (s.charAt(i) == s.charAt(j) && (length < 2 || dp[i + 1][j - 1])) {
dp[i][j] = true;
if (length + 1 > longest.length()) {
longest = s.substring(i, j + 1);
}
}
}
}
return longest;
}
public static void main(String[] args) {
String s = "forgeeksskeegfor";
System.out.println("Longest Palindromic Substring (DP): " + longestPalindromeDP(s));
}
}
Time Complexity: O(n²) – Filling the 2D table.
Space Complexity: O(n²) – For storing the dp
table.
4. Manacher’s Algorithm (Optimal Solution)
Manacher’s Algorithm solves the problem in linear time, O(n)
, by transforming the original string to account for even and odd-length palindromes uniformly.
Algorithm
- Preprocess the string to handle both even and odd lengths.
- Use a helper array to store the radius of the longest palindrome centered at each position.
- Utilize symmetry to avoid redundant checks.
Java Implementation
public class LongestPalindromicSubstring {
// Manacher's Algorithm for finding the longest palindromic substring
public static String longestPalindromeManacher(String s) {
if (s == null || s.length() == 0) {
return "";
}
// Preprocess the input string to handle even-length palindromes
String processedString = preprocessString(s);
int n = processedString.length();
int[] p = new int[n]; // Array to store the radius of the palindrome centered at each index
int center = 0, rightBoundary = 0;
// Variables to keep track of the maximum length palindrome found
int maxLength = 0, centerIndex = 0;
for (int i = 0; i < n; i++) {
// Find the corresponding position to i around the current center
int mirror = 2 * center - i;
// If within the current right boundary, initialize p[i] with the minimum of either:
// the remaining distance to the right boundary or the mirrored radius
if (rightBoundary > i) {
p[i] = Math.min(rightBoundary - i, p[mirror]);
}
// Attempt to expand the palindrome centered at i
while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 &&
processedString.charAt(i + p[i] + 1) == processedString.charAt(i - p[i] - 1)) {
p[i]++;
}
// If the expanded palindrome goes beyond the current right boundary, adjust center and boundary
if (i + p[i] > rightBoundary) {
center = i;
rightBoundary = i + p[i];
}
// Track the maximum length palindrome and its center
if (p[i] > maxLength) {
maxLength = p[i];
centerIndex = i;
}
}
// Extract the longest palindrome from the processed string
int start = (centerIndex - maxLength) / 2; // Convert back to the original string indices
return s.substring(start, start + maxLength);
}
// Preprocess the input string by inserting special characters (#) to handle even-length palindromes
private static String preprocessString(String s) {
StringBuilder sb = new StringBuilder();
sb.append('^'); // Start with a special character to avoid boundary checks
for (char c : s.toCharArray()) {
sb.append('#').append(c);
}
sb.append("#$"); // End with special characters
return sb.toString();
}
public static void main(String[] args) {
String s = "babad";
System.out.println("Longest Palindromic Substring (Manacher's Algorithm): " + longestPalindromeManacher(s));
String s2 = "forgeeksskeegfor";
System.out.println("Longest Palindromic Substring (Manacher's Algorithm): " + longestPalindromeManacher(s2));
}
}
Explanation
- Preprocessing: The original string
s
is transformed by inserting a special character (e.g.,#
) between each character, including boundaries. This transformation (preprocessString
) allows the algorithm to handle even and odd-length palindromes uniformly.- Example:
"babad"
becomes"^#b#a#b#a#d#$"
.
- Example:
- Palindrome Expansion: Use an array
p
to store the radius of the palindrome centered at each character in the transformed string. - Symmetry: If the current position
i
is within the right boundary of the current longest palindrome, the value ofp[i]
is initialized using the value of the mirrored position relative to the current center. - Center Expansion: If the palindrome centered at
i
expands beyond the current right boundary, update the center and right boundary. - Extract Result: Convert the longest palindrome found in the processed string back to the original indices.
Time Complexity: O(n)
Space Complexity: O(n)
Conclusion
The Longest Palindromic Substring problem has a variety of solutions. Starting with a brute-force approach gives insight into the problem structure. Expanding around the center offers a significant performance boost, while dynamic programming is more systematic. For optimal efficiency, Manacher’s algorithm is the way to go.
By understanding these different techniques, you are better equipped to tackle similar problems involving substrings and optimization.
Feel free to ask questions or share your code snippets in the comments!