Palindromic Substrings

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".

Intuition

It's not always storing what the question asking (number of palindromic) in the dp array. What we could do is we can simply go through everything and mark if a substring is palindromic or not.

Similar to Longest Palindrome Substring > 1. Store the result of if current substring is palindrome

class App:
    def countSubstrings(self, s: str) -> int:
        if len(s) == 0: return 0

        countPalindromes = len(s)

        dp = [[False for _ in range(len(s))] for _ in range(len(s))]

        self.intialiseDp(dp)

        for length in range(2, len(s) + 1):
            start = 0
            end = start + length - 1

            while (end < len(s)):
                if (s[start] == s[end]) and self.betweenIsPalindrome(dp, start, end):
                    dp[start][end] = True
                    countPalindromes += 1
                
                start += 1
                end += 1
        
        return countPalindromes

    def intialiseDp(self, dp: List[List[int]]):
        for i in range(len(dp)):
            dp[i][i] = True
    
    def betweenIsPalindrome(self, dp, start, end):
        return dp[start + 1][end - 1] or start + 1 >= end - 1

Time complexity: $O(n^2)$
Space complexity: $O(n^2)$