Count of Palindromic Substrings
Explore methods to count all palindromic substrings within a string by using naive recursion and optimized dynamic programming approaches. Understand how memoization and bottom-up tabulation reduce time complexity from exponential to quadratic, improving performance for larger inputs.
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.
function countPalindromicSubstring(str1){// Write your code herereturn 0;}export{countPalindromicSubstring};
Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms ...