Count of Palindromic Substrings
Explore methods to count palindromic substrings within a string by understanding naive recursive solutions and optimizing them with dynamic programming. Learn to implement both top-down memoization and bottom-up tabulation approaches to efficiently solve this problem with improved time complexity.
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 str1consists of the same case English letters.
Examples
No. | str1 | Palindromic Substrings | Count of Palindromic Substrings |
1 | pqr | "p", "q", "r" | 3 |
2 | aaa | "a", "a", "a", "aa", "aa", "aaa" | 6 |
Try it yourself
Implement your solution in the following playground.
int CountPalindromicSubstring(string str1){return 0;}
Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms ...