.

Solution

Method 1 – Top-Down Dynamic Programming with Memoization

Intuition

The problem asks for the count of distinct palindromic subsequences. Since subsequences can overlap and repeat, we need to avoid double-counting. By using DP with memoization, we can efficiently count unique palindromic subsequences in all substrings, leveraging overlapping subproblems.

Approach

Define a recursive function dp(l, r) that returns the number of distinct palindromic subsequences in the substring s[l:r+1].
Use memoization to cache results for each (l, r) to avoid recomputation.
For each character ch in 'a'..'d':

Find the first (i) and last (j) occurrence of ch in s[l:r+1].
If i > j, skip (character not present).
If i == j, only one palindromic subsequence: the single character.
If i < j, count two palindromic subsequences (

Related Tags