# Solution: Palindromic Substrings

Let's solve the Palindromic Substrings problem using the Dynamic Programming pattern.

## Statement

Given a string, `s`

, return the number of palindromic substrings contained in it. A **substring** is a contiguous sequence of characters in a string. A palindrome is a phrase, word, or sequence that reads the same forward and backward.

**Constraints:**

$1 \leq$ `s.length`

$\leq 1000$ `s`

consists of only lowercase English characters.

## Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.

### Naive approach

A naive approach to this problem is to find all possible substrings and count the number of palindromic substrings. For example, consider the string “deed”. The number of substrings contained in “deed” is 10: “d”, “e”, “e”, “d”, “de”, “ee”, “ed”, “dee”, “eed”, and “deed”. Out of these 10 substrings, six are palindromes: “d”, “e”, “e”, “d”, “ee”, and “deed”. Therefore, the number of palindromic substrings in “deed” is six.

We get the required result, but at what cost? Since we’re checking every possible substring, the total number of substrings in a string of length

### Optimized approach using dynamic programming

If we look at the example above, we notice that any substring of length `dp`

, of size `dp[i][j]`

will store whether the string `s[i..j]`

is a palindromic substring. If the cell `dp[i][j]`

holds the result of the earlier computation, we will utilize it in

First, we initialize a

`count`

variable with$0$ , which will count the number of palindromic substrings in`s`

.A lookup table is initialized with FALSE.

**Base case 1:**The diagonal in the lookup table is populated with TRUE because any cell in the diagonal corresponds to a substring of length one, and any string of length one is always a palindrome. The number of one-letter palindromic strings (i.e., the number of elements in the diagonal) is also added to the`count`

.**Base case 2:**We check whether all two-letter substrings are palindromes and update the`count`

and`dp`

accordingly. We do this by iterating over the string, comparing`s[i]`

and`s[i+1]`

, and storing the result at`dp[i][i+1]`

. After that, we also increment the`count`

if the value of`dp[i][i+1]`

is TRUE, which tells us that the two-letter substring was a palindrome.After these base cases, we check all substrings of lengths greater than two. However, we only compare the first and the last characters. The rest of the string is checked using the lookup table. For example, for a given string “zing”, we want to check whether “zin” is a palindrome. We’ll only compare ‘z’ and ‘n’ and check the value of

`dp[1][1]`

, which will tell whether the remaining string “i”, represented by`s[1..1]`

, is a palindrome. We’ll take the logical AND of these two results and store it at`dp[0][2]`

because “zin” is represented by the substring`s[0..2]`

. This way, we’ll avoid redundant computations and check all possible substrings using the lookup table.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.