Palindrome Counting - Dynamic Programming / Interval

Problems
1

https://algo.monster/problems/palindrome_counting

2

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

3

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

4

Thank you for pointing out. We will fix it.

5

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

6 
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
7

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
8

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
9

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

}