<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:
        cache = {}
        def isPalindrome(st):
            if st in cache:
                return cache[st]
            if len(st) <= 1:
                return True

            l = 0
            r = len(st) - 1

            while l < r:
                if st[l] != st[r]:
                    cache[st] = False
                    return False
                l += 1
                r -= 1
            cache[st] = True
            return True
        
        if len(s) == 0:
            return 0
        
        res = len(s)
        for l in range(len(s)):
            for r in range(l + 1, len(s)):
                if s[r] != s[l]:
                    continue
                if isPalindrome(s[l:r + 1]):
                    res += 1
        return res

            
64138