# Python Program to Count all Palindrome Sub Strings in a String

A word, phrase, or sentence is said to be a palindrome if that reads the same backward as forwards. In this article, we will learn how to count all the palindrome substring in the given string in Python.

Example

```Input: abbaab
Output: 4
Explanation:
All the substring palindrome are
"bb", "abba", "aa", "baab"```

We are going to solve this by using Top-Down Dynamic Programming.

## Count all Palindrome Sub Strings in a String

1. Get user input.

2. Iterate the array and generate all possible substring.

3. Call the function is_palindrome to check whether the substring is a palindrome.

4. Check the base condition in the is_palindrome function and check for each and every i, j, if characters are equal.

5. Recursively call the is_palindrome function.

6. If the substring is palindrome increment count by 1.

7. Finally, return the count.

Below is the Python code:

```dp = [[-1 for i in range(1000)] for j in range(1000)]

def is_palindrome(s, i, j):
# base condition
if (i > j):
return 1

if (dp[i][j] != -1):
return dp[i][j]

if (s[i] != s[j]):
dp[i][j] = 0
return dp[i][j]
dp[i][j] = is_palindrome(s, i + 1, j - 1)

return dp[i][j]

def count_substrings(s):
n = len(s)
count = 0
for i in range(n):
for j in range(i + 1, n):
if (is_palindrome(s, i, j)):
count += 1
return count

s = input("Enter the string: ")
print("The total possible number of palindrome substring is",count_substrings(s))
```

Output

```Enter the string: abbab
The total possible number of palindrome substring is 3

Enter the string: ab
The total possible number of palindrome substring is 0```