647. Palindromic Substrings

Medium

---

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

• 1 <= s.length <= 1000

• s consists of lowercase English letters.

Solution : This solution is same as of used in Problem 5 : Longest Plaindrome Substring

class Solution:
    def countSubstrings(self, s: str) -> int:
        # Using Same Solution as in PB5 : Longest Palindrome Substring
        dp = [[False]*len(s) for _ in range(len(s))]
        count = 0
        for index in range(len(s)):
            dp[index][index] = True
            count += 1 # Each Character itself is substring
        for i in range(len(s)-1, -1 , -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    if (j-i) == 1 or dp[i+1][j-1] is True:
                        dp[i][j] = True
                        count += 1
        return count