Longest Palindromic Substring refers to finding the longest contiguous substring in a given string that is a palindrome, which is a sequence of characters that reads the same backward as forward.
For example, in the string “babad”, the longest palindromic substring is “bab”, which is a palindrome because it reads the same backward as forward. Another example would be the string “cbbd”, which has a longest palindromic substring of “bb”.
To solve this problem, we can use the dynamic programming approach by creating a 2D boolean array to store whether a substring is a palindrome or not.
The diagonal of the array is set to true, and we iterate over the upper triangle of the array, checking whether each substring is a palindrome or not. If a substring is a palindrome, we mark it as true in the array and update the length of the longest palindrome found so far.
Approach 1: Brute Force
The simplest approach to finding the Longest Palindromic Substring is to generate all possible substrings of the given string and check whether each substring is a palindrome or not. This approach has a time complexity of O(n^3), where n is the length of the input string.
Here is the pseudocode for the brute force approach:
function longest_palindromic_substring(string):
n = length(string)
longest_substring = ""
for i = 0 to n - 1 do:
for j = i to n - 1 do:
substring = string[i..j]
if is_palindrome(substring) and length(substring) > length(longest_substring) do:
longest_substring = substring
return longest_substring
In this code, we iterate over all possible substrings of the input string and check whether each substring is a palindrome or not. We keep track of the longest palindromic substring found so far and return it at the end.
Approach 2: Dynamic Programming
A more efficient approach to finding the Longest Palindromic Substring is to use dynamic programming. We can create a 2D boolean array dp
, where dp[i][j]
is true if the substring string[i..j]
is a palindrome and false otherwise. We can use this array to avoid repeated palindrome checks and reduce the time complexity of the algorithm to O(n^2).
Here is the pseudocode for the dynamic programming approach:
function longest_palindromic_substring(string):
n = length(string)
longest_substring = ""
dp = [[false] * n for i in range(n)]
for i = n - 1 to 0 do:
for j = i to n - 1 do:
if string[i] == string[j] do:
if j - i <= 1 or dp[i+1][j-1] do:
dp[i][j] = true
if j - i + 1 > length(longest_substring) do:
longest_substring = string[i..j]
return longest_substring
In this code, we initialize the dp
array and iterate over all possible substrings of the input string. We check whether each substring is a palindrome or not by using the dp
array, which stores whether a substring is a palindrome or not. If we find a palindromic substring, we update the longest_substring
variable if the length of the current substring is greater than the length of the longest palindromic substring found so far.
Approach 3: Expand Around Center
Another approach to finding the Longest Palindromic Substring is to use the Expand Around Center algorithm. We can iterate over all possible centers of palindromes in the input string and expand around each center to check whether we can find a palindromic substring. This approach has a time complexity of O(n^2) and is more efficient than the brute force approach.
Here is the pseudocode for the Expand Around Center algorithm:
function longest_palindromic_substring(string):
n = length(string)
longest_substring = ""
for i = 0 to n - 1 do:
substring_odd = expand_around_center(string, i, i)
substring_even = expand_around_center(string, i, i + 1)
if length(substring_odd) > length(longest_substring) do:
longest_substring = substring_odd
if length(substring_even) > length(longest_substring) do:
longest_substring = substring_even
return longest_substring
function expand_around_center(string, left, right):
n = length(string)
while left >= 0 and right < n and string[left] == string[right] do:
left -= 1
right += 1
return string[left+1..right-1]
Among the three approaches discussed, the dynamic programming approach is the most efficient and recommended for finding the Longest Palindromic Substring.
The brute force approach has a time complexity of O(n^3), which is too slow for most practical applications. It involves generating all possible substrings of the input string and checking whether each substring is a palindrome or not, which results in a lot of redundant computations.
The Expand Around Center algorithm has a time complexity of O(n^2), which is better than the brute force approach. However, it requires more code and is more difficult to implement than the dynamic programming approach.
The dynamic programming approach has a time complexity of O(n^2), which is the same as the Expand Around Center algorithm.
However, it is more efficient because it avoids redundant computations by using a 2D boolean array to store whether a substring is a palindrome or not.
This approach has a simple and concise implementation and is suitable for large input strings.
Therefore, if efficiency is a concern, the dynamic programming approach is the best choice for finding the Longest Palindromic Substring.
Longest Palindromic Substring: Java Solution
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
String res = "";
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1]);
if (dp[i][j] && j - i + 1 > res.length()) {
res = s.substring(i, j + 1);
}
}
}
return res;
}
In this code, we first initialize the 2D boolean array dp
, where dp[i][j]
is true if the substring s[i..j]
is a palindrome and false otherwise. We then iterate over all possible substrings of the input string s
using two nested loops.
For each substring, we check whether it is a palindrome or not using the dp
array. If we find a palindromic substring whose length is greater than the length of the current longest palindromic substring found so far, we update the res
variable.
Finally, we return the res
variable, which contains the longest palindromic substring found.
Longest Palindromic Substring: JavaScript Solution
function longestPalindrome(s) {
const n = s.length;
const dp = new Array(n).fill(0).map(() => new Array(n).fill(false));
let res = '';
for (let i = n - 1; i >= 0; i--) {
for (let j = i; j < n; j++) {
dp[i][j] = s[i] === s[j] && (j - i <= 2 || dp[i + 1][j - 1]);
if (dp[i][j] && j - i + 1 > res.length) {
res = s.slice(i, j + 1);
}
}
}
return res;
}
The JavaScript implementation of the dynamic programming approach for finding the Longest Palindromic Substring is similar to the Java implementation.
We first initialize the 2D boolean array dp
, where dp[i][j]
is true if the substring s[i..j]
is a palindrome and false otherwise. We then iterate over all possible substrings of the input string s
using two nested loops. For each substring, we check whether it is a palindrome or not using the dp
array.
If we find a palindromic substring whose length is greater than the length of the current longest palindromic substring found so far, we update the res
variable. Finally, we return the res
variable, which contains the longest palindromic substring found.
Longest Palindromic Substring: Python Solution
def longestPalindrome(s: str) -> str:
n = len(s)
dp = [[False] * n for _ in range(n)]
res = ''
for i in range(n - 1, -1, -1):
for j in range(i, n):
dp[i][j] = s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1])
if dp[i][j] and j - i + 1 > len(res):
res = s[i:j + 1]
return res
In this code, we first initialize the 2D boolean array dp
, where dp[i][j]
is true if the substring s[i..j]
is a palindrome and false otherwise. We then iterate over all possible substrings of the input string s
using two nested loops.
For each substring, we check whether it is a palindrome or not using the dp
array. If we find a palindromic substring whose length is greater than the length of the current longest palindromic substring found so far, we update the res
variable.
Finally, we return the res
variable, which contains the longest palindromic substring found.
Longest Palindromic Substring: Ruby Solution
def longest_palindrome(s)
n = s.length
dp = Array.new(n) { Array.new(n, false) }
res = ''
(n - 1).downto(0) do |i|
(i...n).each do |j|
dp[i][j] = s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1])
if dp[i][j] && j - i + 1 > res.length
res = s[i..j]
end
end
end
res
end
The Ruby implementation of the dynamic programming approach for finding the Longest Palindromic Substring is similar to the Python implementation.
We first initialize the 2D boolean array dp
, where dp[i][j]
is true if the substring s[i..j]
is a palindrome and false otherwise. We then iterate over all possible substrings of the input string s
using two nested loops. For each substring, we check whether it is a palindrome or not using the dp
array.
If we find a palindromic substring whose length is greater than the length of the current longest palindromic substring found so far, we update the res
variable. Finally, we return the res
variable, which contains the longest palindromic substring found.