Count all palindromic subsequences

Hard

Problem

Return how many subsequences of the string are palindromes. Subsequences taken from different index sets count separately, even if they spell the same thing.

Example 1

Input:  "abcd"
Output: 4

Example 2

Input:  "aab"
Output: 4

"a", "a", "b" and "aa".

Also asked as: Count All Palindromic Subsequence in a given String

Test cases

Case 1

Input:    "abcd"
Expected: 4

Case 2

Input:    "aab"
Expected: 4

Case 3

Input:    "aaa"
Expected: 7

Case 4

Input:    "a"
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Interval DP

Time O(n²)Space O(n²)

dp[i][j] = count in s[i..j]. dp[i][j] = dp[i+1][j] + dp[i][j-1] − dp[i+1][j-1], and +dp[i+1][j-1]+1 when s[i]===s[j].

function countPalindromicSubseq(s) {
const n = s.length;
const dp = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = 0; i < n; i++) dp[i][i] = 1;
for (let len = 2; len <= n; len++) {
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0);
if (s[i] === s[j]) dp[i][j] += 1 + (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0);
}
}
return dp[0][n - 1];
}