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.
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))
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