# 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

## Leave a Reply