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(n3)

• 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(n2)

• Space complexity: O(n2)