A palindrome is a string that reads the same forward and backward. a substring is a contiguous subset of characters in a string. Given a string s how many distinct substrings of s are palindromes

Here is the Python program to compute how many distinct substrings of a string s are palindromes:

def AllPalindromes(s, l, h, sub):  #function that finds all the palindromes

while l >= 0 and h < len(s) and s[l] == s[h]:  #the loop iterates and reads the s until s[l.h] is a palindrome

 sub.add(s[l: h + 1])  #adds the palindromes to sub

 l = l - 1  #decrements the count of l by 1

 h = h + 1 #increments the count of h by 1

def DistinctPalindromes(s):  #function to find all distinct palindromic substrings of s and also their number

substr = set()  #stores all distinct substrings of s which are palindromes

for i in range(len(s)):  #iterates through s

 AllPalindromes(s, i, i,substr) # find all  palindromes with odd length and with s[i] as mid point

 AllPalindromes(s, i, i + 1, substr) # find all  palindromes with even length and with s[i] as mid point

print("palindromic substrings are",substr, '\n',end='')  # display all distinct palindromic substrings

print(len(substr),"distinct substrings of",s,"are palindromes") # display the number of distinct palindromic substrings

print("Enter a string:")  #prompts user to enter a string

s = input()  #accepts input from user

DistinctPalindromes(s)  #calls DistinctPalindromes method by passing input string to it in order to compute the

Explanation:

The program is well explained in the comments attached with each statement of the code. The function AllPalindromes finds all the palindromes of string s. while loop iterates and reads the string forward and backward to find same i.e. palindrome. Here h and l represents high and low part of the string s. They can also be called as forward and backward pointers to the s characters. The while condition also checks the characters at s[l] position in the string s is equal to the character at s[h].  add() method is used to push all palindromes into the set  sub. The function DistinctPalindromes is used to find all the distinct substrings of s that are palindromes. The loop iterates through characters of string s and calls AllPalindromes method to find all palindromes with odd and even length. It then prints the distinct palindromic substrings . For examples s = "aabaa" then the palindromic substrings are {'aabaa', 'b', 'aba', 'a', 'aa'}  and the number of distinct substrings of aabaa that are palindromes is 5. The program along with its output is attached in a screenshot.