Distinct Palindromic Subsequences
HardDynamic ProgrammingStringMath
Description
Given a non-empty string s, return the number of distinct non-empty palindromic subsequences of s, modulo 10^9 + 7.
Examples
Input:
s = "bccb"Output:
6Explanation:
Distinct palindromic subsequences of 'bccb' are b, c, bb, cc, bcb, bccb — six in total.
Input:
s = "a"Output:
1Explanation:
The only non-empty palindromic subsequence of the string 'a' is 'a' itself, so the count is 1.
Input:
s = "aaa"Output:
3Explanation:
Distinct palindromic subsequences of 'aaa' are a, aa, aaa — three in total.
Constraints
- •
1 ≤ s.length ≤ 200 - •
s consists of lowercase English letters.