Count Different Palindromic Subsequences

Given a string s, return the number of distinct non-empty palindromic subsequences in s. Pattern focus: Palindrome DP. This is a harder counting variant where duplicates must be handled carefully across intervals.

Input Format

s = input string

Output Format

number of distinct non-empty palindromic subsequences

Constraints

  • 1 <= s.length <= 1000
  • s contains lowercase English letters.

Examples

Example 1:

Input:

s = "bccb"

Output:

6

Explanation:

This is a standard example for counting distinct palindromic subsequences.

Example 2:

Input:

s = "aaa"

Output:

3

Explanation:

The distinct palindromic subsequences are a, aa, and aaa.

Loading...
Count Different Palindromic Subsequences