# Palindrome Counting - Dynamic Programming / Interval

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);
}
``````

}