Count all palindromic subsequences
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
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];}