Instead of directly jumping into the problem, Let’s understand, What is **Longest Palindromic Substring** and **Dynamic Programming**.

## What is the Longest Palindromic Substring

Finding the longest substring within a given string that reads the same **backwards as forward**. A substring is a **contiguous sequence of characters** within a string.

A **palindrome** is a string that reads the same backwards as forward. For example, “**madam**“, “**racecar**“, and “**a**” are palindromes. The task is to identify the longest such sequence within a given string. To solve this problem we can use several methods, including **dynamic programming, expanding around the centre, and Manacher’s algorithm**. But in this article, we are using Dynamic Programming.

Let’s understand first what is **Dynamic Programming (DP)**

## What is the Dynamic Programming (DP)

Dynamic Programming (DP) is a method for solving complex problems by **breaking them down into smaller subproblems**. It is particularly useful for optimization problems where the solution can be constructed efficiently by solving overlapping subproblems and storing their solutions.

Dynamic Programming divided into **4 Key Concepts**

- Optimal Substructure
- Overlapping Subproblems
- Memoization
- Tabulation

Enough Talking about DP and Palindromic Substring. Let’s jump into problem.

### Problem Statement

Given a string `s`

, find the longest substring that is a palindrome.

#### Input

`A string s of length n`

#### Output

`The longest palindromic substring in s.`

#### Constraints

`1 ≤ n ≤ 1000`

#### Example Scenarios

```
Input: babad
Output: bab (or aba)
```

**To solve this problem using dynamic programming, we can use a 2D table to keep track of palindromic substrings.**

#### Code

Let’s see how can we solve this problem using python.

```
def longest_palindromic_substring(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
start, max_length = 0, 1
for i in range(n):
dp[i][i] = True
for i in range(n - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
start = i
max_length = 2
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
start = i
max_length = length
return s[start:start + max_length]
# Example usage
print(longest_palindromic_substring("babad")) # Output: "bab" or "aba"
print(longest_palindromic_substring("cbbd")) # Output: "bb"
```

### Testing and Edge Cases

`s = "a"`

-> Output:`"a"`

`s = "ac"`

-> Output:`"a"`

or`"c"`

`s = "racecar"`

-> Output:`"racecar"`

`s = "forgeeksskeegfor"`

-> Output:`"geeksskeeg"`

### Complexity Analysis

**Time Complexity**: O(n^2)**Space Complexity**: O(n^2)