Longest Palindromic Substring

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.

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

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.