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