<p>Given a string <code>s</code>, return <em>the number of <strong>palindromic substrings</strong> in it</em>.</p>

<p>A string is a <strong>palindrome</strong> when it reads the same backward as forward.</p>

<p>A <strong>substring</strong> is a contiguous sequence of characters within the string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abc&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> Three palindromic strings: &quot;a&quot;, &quot;b&quot;, &quot;c&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aaa&quot;
<strong>Output:</strong> 6
<strong>Explanation:</strong> Six palindromic strings: &quot;a&quot;, &quot;a&quot;, &quot;a&quot;, &quot;aa&quot;, &quot;aa&quot;, &quot;aaa&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

# class Solution:
#     def countSubstrings(self, s: str) -> int:
#         def isPalindrome(s):
#             return s == s[::-1]
        
#         def findAllPalindromes(l, r):
#             if l >= r:
#                 return 0
            
#             if cache[l][r] != -1:
#                 return 0
            
#             count = 0
#             if isPalindrome(s[l:r]):
#                 count += 1
            
#             cache[l][r] = count + findAllPalindromes(l + 1, r) + findAllPalindromes(l, r - 1)
#             return cache[l][r]
        
#         n = len(s)
#         cache = [[-1 for i in range(n + 1)] for j in range(n + 1)]
    


#         return findAllPalindromes(0, n)

class Solution:

    def countSubstrings(self, s: str) -> int:
        def count(i, j):
            if j < i or i < 0 or j >= len(s):
                return 0
            if memo[i][j] != -1:
                return memo[i][j]
            if i == j:
                return 1

            memo[i][j] = count(i + 1, j) + count(i, j - 1) - count(i + 1, j - 1)
            if s[i] == s[j] and palindrome[i + 1][j - 1]:
                palindrome[i][j] = True
                memo[i][j] += 1
            return memo[i][j]

        n = len(s)
        palindrome = [[] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                palindrome[i].append(j <= i)
        memo = [[-1] * n for _ in range(n)]
        
        return count(0, n - 1)
108665