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 66

Note: This problem has a direct application in bioinformatics. It is used in the analysis of DNA and RNA.

Constraints:

  • 11 \leq str1.length 150\leq 150
  • str1 consists of the same case English letters.

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.