I think question should add one more info that we are looking palindromes in substrings and not subsequences.

The testcase ‘aa’ failed, it should be 3 rather than 0

Thank you for pointing out. We will fix it.

Hey, please can you provide top down solutions for the interval problems ? They are relatively easier to reason than the bottom up approaches.

```
n = len(s)
dp =[[False] *n for _ in range(n)]
count = n
for i in range(n):
dp[i][i] = True
for i in range(n-2, -1, -1):
for j in range(i+1,n):
if s[i] == s[j]:
if dp[i+1][j-1] or j-i == 1:
dp[i][j] = True
count += 1
print(dp)
return count
```

This problem is written slight difference for the better understanding of next problem which extension this problem

```
n = len(s)
dp =[[False] *n for _ in range(n)]
ans = 0
for i in range(n):
dp[i][i] = True
ans += 1
for l in range(2, n+1):
#starting of the string
for i in range(n-l+1):
j = i+l-1 #ending index
if l == 2:
dp[i][j] = (s[i] == s[j])
if dp[i][j]:
ans += 1
else:
dp[i][j] = ((s[i] == s[j]) and dp[i+1][j-1])
if dp[i][j]:
ans += 1
return ans
```

def palindrome_counting(s: str) → int:

```
ln = len(s)
c = 0
for i in range(ln):
l = i
r = i
while l >= 0 and r < ln:
if s[l] == s[r]:
c += 1
l -= 1
r += 1
else:
break
for i in range(ln-1):
l=i
r=i+1
while l >= 0 and r < ln:
if s[l] == s[r]:
c += 1
l -= 1
r += 1
else:
break
return c
```

Here’s my top-down solution:

import java.util.Scanner;

import java.util.HashMap;

class Solution {

```
public static HashMap<String, Integer> memo = new HashMap<>();
public static int palindromeCounting(String s) {
if(s.length() == 0)
return 0;
if(s.length() == 1)
return 1;
Integer cur = memo.get(s);
if(cur != null) {
return cur;
} else {
cur = (isPalindrome(s) ? 1 : 0);
cur += palindromeCounting(s.substring(0, s.length()-1));
cur += palindromeCounting(s.substring(1, s.length()));
cur -= palindromeCounting(s.substring(1, s.length()-1));
memo.put(s,cur);
return cur;
}
}
public static boolean isPalindrome(String s) {
int left = 0; int right = s.length()-1;
while (left < right) {
if(s.charAt(left) != s.charAt(right))
return false;
left++;
right--;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
scanner.close();
int res = palindromeCounting(s);
System.out.println(res);
}
```

}