hardDynamic Programming 2DPure DSA~50 min
Count Distinct Palindromic Subsequences
Given a sequence drawn from a tiny alphabet, count how many DISTINCT non-empty palindromic subsequences it contains — distinctness is by content, not by index positions.
Problem
Given a string s consisting only of the characters 'a', 'b', 'c', and 'd', return the number of distinct non-empty palindromic subsequences of s. Since the answer may be very large, return it modulo 1e9 + 7.
Input
A string s of length [1, 1000] over the alphabet {a, b, c, d}.
Output
An integer: the count of distinct palindromic subsequences mod 1e9+7.
Constraints
- 1 <= s.length <= 1000
- s[i] is one of 'a', 'b', 'c', 'd'.
Examples
Example 1
Input
s = "bccb"
Output
6
Distinct palindromic subsequences: b, c, bb, cc, bcb, bccb.
Example 2
Input
s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"
Output
104860361
Large count reduced modulo 1e9+7.