### Problem

- Given a string
`S`

- Write an algorithm to find the longest palindromic substring in
`S`

- Palindromic string reads the same backwards. A character itself is a palindrome

### 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

#### Implementation

```
```

#### Complexity

- 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]`

value as`true`

if substring at`i`

and`j`

is palindrome, starting with one, two letters and so onAt each iteration, remember the substring's start index and max length to find the longest palindromic substring

#### Implementation

```
```

#### Complexity

- Time complexity: O(n
^{2}) - Space complexity: O(n
^{2})