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

```
```

- Output

```
anana
bb
a
```

Time complexity: O(n

^{3})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 substringsAt each iteration, remember the substring's start index and max length to find the longest palindromic substring

```
```

- Output

```
a
bb
ccc
anana
```

Time complexity: O(n

^{2})Space complexity: O(n

^{2})