Count of Palindromic Substrings
Let's solve the Count of Palindromic Substrings problem using Dynamic Programming.
Statement
Given a string str1
, find the count of palindromic substrings in it.
A string is said to be a palindrome if it can be read the same backward and forward. For example, “madam” is a palindrome because it can be read the same from left to right and right to left.
A substring is a sequence of consecutive characters from a string. For example, “way” is a substring of “subway”.
For example, if we have a string “aaa”, the palindromic substrings and its count will be:
- “a”, “a”, “a”, “aa”, “aa”, “aaa”
- Count of palindromic substrings will be equal to
Note: This problem has a direct application in bioinformatics. It is used in the analysis of DNA and RNA.
Constraints:
-
str1.length
str1
consists of the same case English letters.
Examples
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.