Longest Palindromic Substring

In this article, you will learn to analyze and resolve the longest palindromic substring problem by using a dynamic programming algorithm

A palindromic is a string that reads the same in both directions. A character itself is a palindrome

Problem

• Given a string s

• Write an algorithm to find the longest palindromic substring in s

Example

• Input: "bananas". Expected output: "anana"

• Input: "bb". Expected output: "bb"

• Input: "a". Expected output: "a"

Approach 1: Brute Force

• Find all substrings in the given string s

• For each substring, check if it is the longest palindrome

public class String_LongestPalindrome_BruteForce {  
    static String findLongestPalindromicSubstring(String s) {
        if(s == null || s.isEmpty()) return "";

        String longestPalindrome = "";
        char[] charArr = s.toCharArray();
        for (int i = 0; i < charArr.length; i++) {
            for (int j = i; j < charArr.length; j++) {
                String substr = s.substring(i, j+1);
                if(isPalindrome(substr) && substr.length() > longestPalindrome.length()) {
                    longestPalindrome = substr;
                }
            }
        }

        return longestPalindrome;
    }

    static boolean isPalindrome(String s) {
        String reversedStr = new StringBuilder(s).reverse().toString();
        return s.equals(reversedStr);
    }

    public static void main(String[] args) {
        System.out.println(findLongestPalindromicSubstring("bananas"));
        System.out.println(findLongestPalindromicSubstring("bb"));
        System.out.println(findLongestPalindromicSubstring("a"));
    }
}

• Output

anana  
bb  
a

• Time complexity: O(n³)

• Space complexity: O(1)

Approach 2: Dynamic Programming

• Given a string bananas, we can say anana is a palindrome thanks to nan is a palindrome and the beginning character is the same with the ending character (a). And so on, nan is a palindrome due to a is a palindrome and the start letter equals to the end letter (n)

  So the optimal substructure is P(i,j) = (S(i) == S(j) && P(i+1,j-1)) with P(i,j) is a palindromic substring from index i to j

  Base cases: P(i,i) = true as a character itself is a palindrome, P(i,i+1) = (S(i) == S(i+1))

• Bottom-up filling P[i][j] matrix value with i is an index of a character in the given string s, j is a length of possible palindrome substrings

  At each iteration, remember the substring's start index and max length to find the longest palindromic substring

public class String_LongestPalindrome_DP {  
    static String findLongestPalindromicSubstring(String s) {
        if(s == null || s.isEmpty()) return "";

        int n = s.length();
        int startIndex = 0;
        int maxLength = 1;
        boolean[][] P = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            P[i][i] = true;
        }

        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i+1)) {
                P[i][i+1] = true;
                startIndex = i;
                maxLength = 2;
            }
        }

        for (int l = 3; l <= n; l++) {
            for (int i = 0; i < n - l + 1; i++) {
                int j = i + l - 1;
                if (s.charAt(i) == s.charAt(j) && P[i+1][j-1]) {
                    P[i][j] = true;

                    if (l > maxLength) {
                        maxLength = l;
                        startIndex = i;
                    }
                }
            }
        }

        return s.substring(startIndex, startIndex + maxLength);
    }

    public static void main(String[] args) {
        System.out.println(findLongestPalindromicSubstring("a"));
        System.out.println(findLongestPalindromicSubstring("bb"));
        System.out.println(findLongestPalindromicSubstring("ccc"));
        System.out.println(findLongestPalindromicSubstring("bananas"));
    }
}

• Output

a  
bb  
ccc  
anana

• Time complexity: O(n²)

• Space complexity: O(n²)